[题解][YZOJ50074] 小 C 的岛屿
仅仅是对 \(O(n^4)\) 做法的一个记录。
简要题意
有 \(N\) 座岛屿，初始时没有边。每座岛屿都有一个概率值 \(p_i\) 和一个大小为 \(s_i\) 友好列表 \(A_i\) 。
小 \(c\) 站在 \(1\) 号岛屿，依次执行以下操作:
\((1)\) 设现在在岛屿 \(x\)，有 \(p_x\) 的概率产生一条图中尚未存在的随机无向边，不会产生自环。
\((2)\) 如果此时所有岛屿仍未联通，她会在当前点的友好列表中，等概率随机选择一个，走到那座岛屿上。并把不满意度增加 \(1\)，然后重复 \((1)\)。否则就结束这个过程
求她的期望不满意度，对一个 \(10^9+7\) 取模.
\(n\le 50\).
解题思路
思考后不难发现，状态只与当前的位置，以及边数相关，那么可以设状态：
\(e(x,i)\) 表示现在位于点 \(x\)，图还差 \(i\) 条边连通，已经走的期望步数。
则最终答案是：
\[Ans = \sum_{i=1}^me(1, i)\cdot P(\text{恰好 }i\text{ 条边连通的概率}) \]不难得到 \(e\) 之间的转移式：
\[e(x,i)=1+\frac{1}{s_x}\sum_{x\rightarrow y}p_x\cdot e(y,i-1)+(1-p_x)\cdot e(y,i) \]如果分层高斯消元是 \(O(n^5)\)，考虑设 \(e(x,i)=c(x)+\sum b(x,y)\cdot e(y,i-1)\) 来递推解决。
带入转移式可得：
\[\begin{aligned} e(x,i)=1+\frac{1}{s_x}\sum_{x\rightarrow y}p_x\cdot e(y,i-1)+(1-p_x)\cdot (\sum_{z=1}^nc(y)+b(y,z)\cdot e(z,i-1))\\ e(x,i)=1+\frac{p_x}{s_x}\sum_{x\rightarrow y}e(y,i-1)+\frac{(1-p_x)}{s_x}\cdot \sum_{x\rightarrow y}(c(y)+\sum_{z=1}^nb(y,z)\cdot e(z,i-1))\\ e(x,i)=1+\frac{(1-p_x)}{s_x}\cdot \sum_{x\rightarrow y}^nc(y)+\frac{p_x}{s_x}\sum_{x\rightarrow y}e(y,i-1)+\frac{(1-p_x)}{s_x}\cdot \sum_{x\rightarrow y}\sum_{z=1}^nb(y,z)\cdot e(z,i-1)\\ \end{aligned} \]于是可以得到两个方程：
\[c(x)=1+\frac{(1-p_x)}{s_x}\cdot \sum_{x\rightarrow y}^nc(y) \]\[b(x,z)=\frac{p_x}{s_x}[x\rightarrow z]+\frac{1-p_x}{s_x}\sum_{x\rightarrow y}b(y,z) \]这样就可以在 \(O(n^4)\) 的高斯消元内得到所有的 \(b,c\)，然后递推得到 \(e(1,i)\)。
接下来考虑如何计算恰好 \(i\) 条边连通的概率，其实要算的就是 \(n\) 个点 \(i\) 条边连通图的方案数。
这类问题的经典处理方式是用斯特林反演来容斥。
于是考虑划分连通块，不同块之间的边不能选择，同一块内的边可选可不选。
这样实际连通块为 \(t\) 的图会在连通块为 \(k\) 的图时算到 \(\begin{Bmatrix}t\\k\end{Bmatrix}\) 次，乘上系数 \((-1)^{k-1}(k-1)!\) ，求和得到连通图。
所以 \(i\) 条边， \(n\) 个点的连通图数量实际上为：
\[\sum_{G}(-1)^{c(G)-1}(c(G)-1)!{e(G) \choose i} \]其中 \(G\) 需要取遍所有的 \(n\) 个点的，划分成了若干连通块的，每个连通块内连成了完全图的图，\(c(G)\) 表示 \(G\) 的连通块数量，\(e(G)\) 表示 \(G\) 的边数。
设 \(dp_{i,j}\) 表示 \(i\) 个点，划分成了若干连通块，每个连通块内部连成完全图后边数和为 \(j\)，的所有图带上容斥系数的 \((-1)^{c(G)-1}(c(G)-1)!\) 之和。
然后考虑一下怎么把系数带上。首先正常的选一个连通块， 然后固定一号连通块在最前面， 然后接着选的时候， 每次不区分选连通块的顺序。那么在转移的时候，考虑下一个连通块的东西是 \(k\)，重标号的系数就是 \(\binom{i+k-1}{k}\)，因为 1 号连通块不能乱排，那么就可以钦定 1 号连通块最前面那个点一直不参与重标号， 于是每种划分方式就会算 \((k-1)!\) 种。
这样可以 \(O(n^4)\) 计算出 \(dp_{n,i}\) ，然后 \(O(n^4)\) 直接算出 \(g_i\)，表示 \(n\) 个点 \(i\) 条边的连通图个数。
namespace Gauss{
int n, a[N][N], b[N];
inline int get(int x){ return (LL) b[x] * qpow(a[x][x], mod - 2) % mod; }
void init(int m){
n = m;
lfor(i, 1, n) b[i] = 0;
lfor(i, 1, n) lfor(j, 1, n) a[i][j] = 0;
}
void solve(){
lfor(i, 1, n){
int inv = qpow(a[i][i], mod - 2);
lfor(j, 1, n) if(i != j){
int K = (LL) inv * a[j][i] % mod;
lfor(k, 1, n) MOD(a[j][k] -= (LL) K * a[i][k] % mod);
MOD(b[j] -= (LL) K * b[i] % mod);
}
}
}
}
using Gauss :: get;
using Gauss :: init;
using Gauss :: solve;
void get_coef(){
init(n);
lfor(x, 1, n){
Gauss :: b[x] = mod - 1;
Gauss :: a[x][x] = mod - 1;
int v = (LL) q[x] * qpow(s[x], mod - 2) % mod;
lfor(j, 1, s[x]) Gauss :: a[x][a[x][j]] = v;
}
solve();
lfor(x, 1, n) c[x] = get(x);
lfor(z, 1, n){
init(n);
lfor(x, 1, n){
int v = (LL) q[x] * qpow(s[x]) % mod;
if(lnk[x][z]) Gauss :: b[x] = Mod(-(LL) p[x] * qpow(s[x]) % mod);
Gauss :: a[x][x] = mod - 1;
lfor(y, 1, n) if(lnk[x][y]) Gauss :: a[x][y] = v;
}
solve();
lfor(x, 1, n) b[x][z] = get(x);
}
lfor(i, 1, m) lfor(x, 1, n){
lfor(y, 1, n) MOD(e[x][i] += (LL) b[x][y] * e[y][i - 1] % mod - mod);
MOD(e[x][i] += c[x] - mod);
}
}
void get_prob(){
lfor(i, 1, n) dp[i][C(i, 2)] = 1;
lfor(i, 1, n) lfor(j, 0, m) if(dp[i][j]) lfor(k, 1, n - i)
MOD(dp[i + k][j + C(k, 2)] += -(LL) dp[i][j] * C(i + k - 1, k) % mod);
lfor(i, 0, m) lfor(j, i, m)
MOD(g[i] += (LL) dp[n][j] * C(j, i) % mod - mod);
lfor(i, 1, m) g[i] = (LL) g[i] * qpow(C(m, i), mod - 2) % mod;
rfor(i, m, 1) MOD(g[i] -= g[i - 1]);
}
signed main(){
read(n), m = n * (n - 1) / 2;
lfor(i, 1, n) read(p[i]), q[i] = Mod(1 - p[i]);
lfor(i, 1, n){
read(s[i]), a[i] = new int[s[i] + 1];
lfor(j, 1, s[i]) read(a[i][j]), lnk[i][a[i][j]] = 1;
}
prep();
get_coef();
get_prob();
lfor(i, 1, m) MOD(Ans += (LL) e[1][i] * g[i] % mod - mod);
cout << Mod(Ans - 1) << endl;
return 0;
}