计蒜客【NOIP2018模拟1】数三角形 <概率>

Problem

【NOIP2018模拟1】数三角形

Description

大家都学过三角形吧。在这个问题里，我们要在随机图里数三角形。首先，我们有一张完全图G，它的边有可能是红色或者蓝色。其中有三种可能的随机性。

1. 某条边 ，以 的概率是红色，以 的概率是蓝色。
2. 对于一组若干条边 ，只有一条边是红色其他是蓝色，且 是红色的概率为 ，满足 。
3. 对于一组若干条边 ，只有一条边是蓝色其他是红色，且 是红色的概率为 ，满足 。

现在你需要找出三条边同色的三角形的期望。

Input

第一行一个数 , 表示G的顶点个数。接下来 行，每行四或五个数字 ，表示点 和 点 之间的边的随机种类是 , 且它对应的概率为 。满足 且 是 到 的实数。保证每条边恰好出现一次。如果 ，则还会有一个输入 ,表示这条边属于那一组。如前面所述，同一组的所有边的概率加起来为 ，且恰好有一条为红色或蓝色。保证每组至少有两条边，且组的编号为从 开始的连续编号。

Output

一行，一个数，表示同色三角形的期望个数，保留两位小数。

Sample Input

Input #1

3
1 2 1 0.5
2 3 1 0.5
3 1 1 0.5

Input #2

3
1 2 1 1
2 3 2 0.5 1
3 1 2 0.5 1

Input #3

4
1 2 1 1
2 3 2 0.5 1
3 1 2 0.5 1
1 4 1 0.4
2 4 3 0.3 2
3 4 3 0.7 2

Sample Output

Output #1

0.25

Output #2

0.00

Output #3

0.55

Constraint

对于 的数据 。
对于另外 的数据，只有第一种随机性。
对于全部数据，，总组数不超过 。

Source

2018 NOIP 提高组模拟赛（一）

标签：概率

Solution

根据这类题的套路，我们可以猜测仍然是通过计算同色角和异色角的期望个数来得到答案。

令同色角期望有个，异色角期望有个，异色三角形期望有个，同色三角形期望有个。由于每个异色三角形都有一个同色角和两个异色角，每个同色三角形都有三个同色角，我们有

化简有。

接下来考虑如何计算和。
同样地，我们枚举每个点，求出以其为顶点的同色角和异色角的期望。
对于一个点，枚举其邻边，

1. 首先计算期望下的总红边数和总蓝边数：
   • 对于一条类边，其是红色的概率为，则对贡献为，对贡献为。
   • 对于属于同一个类边组的边，设其是红色的概率为，那么有的概率在这些边中出现条红边和条蓝边，有的概率在这些边中出现条红边和条蓝边。于是其对的贡献为，对的贡献为。
   • 对于属于同一个类边组的边，设其是蓝色的概率为，。类似地，其对的贡献为，其对的贡献为。
2. 然后对于每个边/边组计算其组成同色角/异色角的期望个数：
   • 对于一条类边，其是红色的概率为，是蓝色的概率为。期望下其他边中有条红边和条蓝边。于是其是红色时，对的贡献为，对的贡献为；是蓝色时，对的贡献为，对的贡献为。
   • 对于属于同一个类边组的边，设其是红色的概率为，。
     期望下在组外的边中有条红边和条蓝边。
     对于某一条边，
     • 若其为红色，则组内的其他边均为蓝色，组内除它以外还有条红边和条蓝边。
       其对的贡献为，
       对的贡献为。
     • 若其为蓝色，
       • 有的概率这组的红边不在这条边之中，此时除它以外还有条红边和条蓝边。
         其对的贡献为，
         对的贡献为。
       • 有的概率这组的红边在除以外的条边中，此时除它以外还有条红边和条蓝边。
         其对的贡献为，
         对的贡献为。
   • 对于属于同一个类边组的边，其情况与类边组大致相同，将交换即可，故不再赘述。

由此，枚举每个点的每条邻边，预先按组编号排序以保证同组的边在一起，扫两次即可计算每条边对和的贡献。
时间复杂度。

Code

#include <bits/stdc++.h>
#define MAX_N 800000
using namespace std;
typedef double dnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n; dnt p[MAX_N+5];
vector <int> G[MAX_N+5];
int id[MAX_N+5], tp[MAX_N+5];
bool cmp(const int &x, const int &y) {return id[x] < id[y];}
int main() {
    read(n); dnt A = 0, B = 0;
    for (int i = 1, u, v, type; i <= n*(n-1)/2; i++) {
        read(u), read(v), read(type), scanf("%lf", p+i);
        if (type > 1) read(id[i]), tp[id[i]] = type;
        G[u].push_back(i), G[v].push_back(i);
    }
    for (int u = 1; u <= n; u++) {
        dnt sA = 0, sB = 0; sort(G[u].begin(), G[u].end(), cmp);
        for (int l = 0, r = 1; l < (int)G[u].size(); l = r+1, r = l+1) {
            if (!id[G[u][l]]) {sA += p[G[u][l]], sB += 1-p[G[u][l]], r = l; continue;}
            for (; r < (int)G[u].size() && id[G[u][l]] == id[G[u][r]]; r++) ; r--;
            dnt ts = 0; for (int i = l; i <= r; i++) ts += p[G[u][i]];
            if (tp[id[G[u][l]]] == 2) sA += ts, sB += (r-l)*ts+(r-l+1)*(1-ts);
            if (tp[id[G[u][l]]] == 3) sA += (r-l)*ts+(r-l+1)*(1-ts), sB += ts;
        }
        for (int l = 0, r = 1; l < (int)G[u].size(); l = r+1, r = l+1) {
            if (!id[G[u][l]]) {
                A += p[G[u][l]]*(sA-p[G[u][l]]);
                A += (1-p[G[u][l]])*(sB-(1-p[G[u][l]]));
                B += (1-p[G[u][l]])*(sA-p[G[u][l]]);
                B += p[G[u][l]]*(sB-(1-p[G[u][l]]));
                r = l; continue;
            }
            for (; r < (int)G[u].size() && id[G[u][l]] == id[G[u][r]]; r++) ; r--;
            dnt ts = 0; for (int i = l; i <= r; i++) ts += p[G[u][i]];
            if (tp[id[G[u][l]]] == 2)
                for (int i = l; i <= r; i++)
                    A += p[G[u][i]]*(sA-ts), 
                    A += (1-ts)*(r-l+sB-(r-l)*ts-(r-l+1)*(1-ts)), 
                    A += (ts-p[G[u][i]])*(r-l-1+sB-(r-l)*ts-(r-l+1)*(1-ts)), 
                    B += p[G[u][i]]*(r-l+sB-(r-l)*ts-(r-l+1)*(1-ts)), 
                    B += (1-ts)*(sA-ts)+(ts-p[G[u][i]])*(1+sA-ts);
            if (tp[id[G[u][l]]] == 3)
                for (int i = l; i <= r; i++)
                    A += p[G[u][i]]*(sB-ts), 
                    A += (1-ts)*(r-l+sA-(r-l)*ts-(r-l+1)*(1-ts)), 
                    A += (ts-p[G[u][i]])*(r-l-1+sA-(r-l)*ts-(r-l+1)*(1-ts)), 
                    B += p[G[u][i]]*(r-l+sA-(r-l)*ts-(r-l+1)*(1-ts)), 
                    B += (1-ts)*(sB-ts)+(ts-p[G[u][i]])*(1+sB-ts);
        }
    }
    return printf("%.2lf\n", A/6-B/12), 0;
}