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

Problem

【NOIP2018模拟1】数三角形

$\mathrm{Time\;Limit:\;1000\;ms}$
$\mathrm{Memory\;Limit:\;262144\;K}$

Description

图论中的三元环也称作三角形。在这个问题里，我们要在随机图里数三角形。

我们有一张完全图G，它的边有可能是红色或者蓝色，有三种可能的随机性：

1. 某条边 $e$ ，以 $p_e$ 的概率是红色，以 $1-p_e$ 的概率是蓝色；
2. 对于一组若干条边 $e_1, e_2, \cdots, e_k$，只有一条边是红色其他是蓝色，且 $e_i$ 是红色的概率为 $p_i$，满足 $\sum^{k}_{i=1}p_i=1$；
3. 对于一组若干条边 $e_1, e_2, \cdots, e_k$，只有一条边是蓝色其他是红色，且 $e_i$ 是红色的概率为 $p_i$，满足 $\sum^{k}_{i=1}p_i=1$。

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

Input

第一行一个数 $n$, 表示G的顶点个数。接下来 $\frac{n(n - 1)}{2}$ 行，每行四或五个数字 $i,j,v,p,(l)$，表示点 $i$ 和 点 $j$ 之间的边的随机种类是 $v$ , 且它对应的概率为 $p$ 。满足 $i \neq j, v \in {1, 2, 3}$ 且 $p$ 是 $0$ 到 $1$ 的实数。保证每条边恰好出现一次。如果 $v > 1$，则还会有一个输入 $l$ ,表示这条边属于那一组。如前面所述，同一组的所有边的概率加起来为 $1$ ，且恰好有一条为红色$(v = 2)$或蓝色$(v = 3)$。保证每组至少有两条边，且组的编号为从 $1$ 开始的连续编号。

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

对于 $30\%$ 的数据 $n < 200$。
对于另外 $30\%$ 的数据，只有第一种随机性。
对于全部数据，$n \le 1200$，总组数不超过 $100000$。

Source

2018 NOIP 提高组模拟赛（一）

标签：概率

Solution

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

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

$$\begin{cases} X+3Y=A\\ 2X=B\\ \end{cases}$$

化简有$Y=\frac{A}{6}-\frac{B}{12}$。

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

1. 首先计算期望下的总红边数$sA$和总蓝边数$sB$：

• 对于一条$1$类边，其是红色的概率为$p$，则对$sA$贡献为$p$，对$sB$贡献为$1-p$。
• 对于属于同一个$2$类边组的边，设其是红色的概率为$p_1,p_2\cdots p_k$，那么有$ts=\sum_{i=1}^{k}p_i$的概率在这些边中出现$1$条红边和$k-1$条蓝边，有$1-ts$的概率在这些边中出现$0$条红边和$k$条蓝边。于是其对$sA$的贡献为$ts$，对$sB$的贡献为$(k-1)\cdot ts+k\cdot (1-ts)$。
• 对于属于同一个$3$类边组的边，设其是蓝色的概率为$p_1,p_2\cdots p_k$，$ts=\sum_{i=1}^{k}p_i$。类似地，其对$sA$的贡献为$(k-1)\cdot ts+k\cdot(1-ts)$，其对$sB$的贡献为$ts$。

2. 然后对于每个边/边组计算其组成同色角/异色角的期望个数：

• 对于一条$1$类边，其是红色的概率为$p$，是蓝色的概率为$1-p$。期望下其他边中有$sA-p$条红边和$sB-(1-p)$条蓝边。于是其是红色时，对$A$的贡献为$p\cdot(sA-p)$，对$B$的贡献为$p\cdot(sB-(1-p))$；是蓝色时，对$A$的贡献为$(1-p)\cdot(sB-(1-p))$，对$B$的贡献为$(1-p)\cdot(sA-p)$。
• 对于属于同一个$2$类边组的边，设其是红色的概率为$p_1,p_2\cdots p_k$，$ts=\sum_{i=1}^{k}p_i$。
  期望下在组外的边中有$sA-ts$条红边和$sB-(k-1)\cdot ts+k\cdot (1-ts)$条蓝边。
  对于某一条边$i$，
  • 若其为红色，则组内的其他边均为蓝色，组内除它以外还有$0$条红边和$k-1$条蓝边。
    其对$A$的贡献为$p_i\cdot(sA-ts)$，
    对$B$的贡献为$p_i\cdot(k-1+sB-(k-1)\cdot ts+k\cdot (1-ts))$。
  • 若其为蓝色，
    • 有$1-ts$的概率这组的红边不在这$k$条边之中，此时除它以外还有$0$条红边和$k-1$条蓝边。
      其对$A$的贡献为$(1-ts)\cdot(k-1+sB-(k-1)\cdot ts+k\cdot (1-ts))$，
      对$B$的贡献为$(1-ts)\cdot(sA-ts)$。
    • 有$ts-p_i$的概率这组的红边在除$i$以外的$k-1$条边中，此时除它以外还有$1$条红边和$k-2$条蓝边。
      其对$A$的贡献为$(ts-p_i)\cdot(k-2+sB-(k-1)\cdot ts+k\cdot (1-ts))$，
      对$B$的贡献为$(ts-p_i)\cdot(1+sA-ts)$。
• 对于属于同一个$3$类边组的边，其情况与$2$类边组大致相同，将$sA,sB$交换即可，故不再赘述。

由此，枚举每个点的每条邻边，预先按组编号排序以保证同组的边在一起，扫两次即可计算每条边对$A$和$B$的贡献。
时间复杂度$\mathcal{O}(n+e)$。

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;
}