【题解】P12992 [GCJ 2022 #1C] Intranets

以此纪念我洛谷 AC 的第 \(999\) 个题。

\(2025.10.09\)

题意：

天网是一张无向图 \(G\) ，包含 \(n\) 个点。一开始，天网上没有任何边。你以等概率随机顺序依次对所有的点对尝试加边。

每次尝试加边 \((u,v)\) 的时候，只有加边前 \(u,v\) 的度数至少一个等于 \(0\) 时，才加入这条边；否则就不加入这条边。

你想要求出尝试完所有点对后，天网的连通块个数为 \(k\) 的概率。对素数 \(p\) 取模。

题解：

更清晰的解答。

我们可以观察到，当一条边 \((u,v)\) 加入时，如果 \(u,v\) 度数都还等于 \(0\) ，那么会使连通块个数 \(+1\) ，其余情况均保持连通块数量不变。

我们记这些边构成集合 \(S\) ，我们需要求的即为 \(|S|=k\) 的概率 \(f(k)\) 。

考虑二项式反演，设钦定 \(k\) 条边 \(\in |S|\) 的概率为 \(g(k)\) 。

则有：

\[g(k)=\sum_{i\geq k}\binom{i}{k} f(i)\\ f(k)=\sum_{i\geq k} \binom{i}{k} (-1)^{i-k}g(i) \]

怎么计算 \(g(k)\) ？

对于一个大小为 \(k\) 的边集 \(S\) ，这些边如果合法那么一定两两没有公共顶点。由于对称性，这些边在原排列中的顺序可以互换。对于 \(S\) 中的一条边 \((u,v)\) ，一定有原排列中排在 \((u,v)\) 前面的边，不包含 \(u\) 和 \(v\) 。

这就有一个树形结构。我们将边集视为顶点，将 \(S\) 中每一条边 \((u_i,v_i)\) 视为一个树根，构成一个森林。

方便起见记集合 \(T\) 为 \(S\) 中所有出现的顶点集合。对于只有一个端点 \(\in T\) 的边，它需要排在 \(S\) 中含有这个顶点的边的后面；对于两段都在 \(T\) 中的边，它需要排在 \(S\) 中两条含有这两个端点的边的后面，在 \(S\) 内排序确定时，即排在两条边更靠后的后面。

因此我们可以建立起父子关系，将不在 \(S\) 中的所有边唯一按照上述方式确定了一个在 \(S\) 中的父亲。我们不妨再取一个点作为超级祖先 \(rt\) ，当作 \(S\) 中所有点的父亲，这样森林就变成了一棵树。

原排列合法，等价于原排列是这棵树的一个拓扑序的逆序。对于一个节点数为 \(N+1\) 的树，其拓扑序共有 \(\displaystyle\frac{(N+1)!}{\prod sz_u}=\frac{N!}{\prod_{u\neq rt}{sz_u}}\) 种 。故原排列合法的概率即为 \(\displaystyle\prod_{u\neq rt} \frac{1}{sz_u}\) 。具体地，对于给定的 \(S\) 的排序 ，这个数为 \(\displaystyle\prod_{i=1}^k \frac{1}{\binom{n}{2}-\binom{n-2i}{2}}=\prod_{i=1}^k\frac{1}{i(2n-2i-1)}\) ，而不同的 \(S\) 的排序会带来不同的树结构，所以概率为 \(\displaystyle k!\times\prod_{i=1}^k\frac{1}{i(2n-2i-1)}=\prod_{i=1}^k\frac{1}{2n-2i-1}\)。

然后我们需要知道，有多少个 \(S\) 满足大小为 \(k\) ，且合法？即为 \(S\) 包含 \(2k\) 个点，然后两两匹配的方案数。共有 \(\displaystyle\binom{n}{2k}(2k-1)!!\) 种。

所以我们心心念念的 \(g(k)\) 就算完了，\(\displaystyle\binom{n}{2k}(2k-1)!!\prod_{i=1}^k\frac{1}{(2n-2i-1)}\) 。

终于可以计算 \(f(k)\) 了：

\[\begin{aligned} f(k)&=\sum_{i\geq k} \binom{i}{k} (-1)^{i-k}g(i) \\ &=\sum_{t=k}^{\lfloor\frac{n}{2}\rfloor} \binom{t}{k}(-1)^{t-k}g(t)\\ &=\sum_{t=k}^{\lfloor\frac{n}{2}\rfloor} \binom{t}{k}(-1)^{t-k} \binom{n}{2t}(2t-1)!!\prod_{i=1}^t\frac{1}{(2n-2i-1)}\\ &=\sum_{t=k}^{\lfloor\frac{n}{2}\rfloor} (-1)^{t-k}\binom{t}{k} \binom{n}{2t}(2t-1)!!\frac{(2n-2t-3)!!}{(2n-3)!!} \end{aligned} \]

时间复杂度线性。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){ll x=0; bool f=1; char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=0; ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48); ch=getchar();}return f?x:-x;
}
inline void write(ll x){if(x<0) x=-x,putchar('-');if(x>9) write(x/10);putchar('0'+x%10);
}
const ll N=10000009;
int inv[2*N],fac[N],finv[N];
int ffac[2*N],ffinv[2*N];
ll n,k,p;
void init(){inv[1]=1;for(ll i=2;i<=2*n;i++){inv[i]=p-1ll*p/i*inv[p%i]%p;}fac[0]=finv[0]=1;for(ll i=1;i<=n;i++){fac[i]=1ll*fac[i-1]*i%p;finv[i]=1ll*finv[i-1]*inv[i]%p;}ffac[1]=1,ffinv[1]=1;for(ll i=3;i<=2*n;i+=2){ffac[i]=1ll*ffac[i-2]*i%p;ffinv[i]=1ll*ffinv[i-2]*inv[i]%p;}
}
inline ll C(ll a,ll b){if(a<b) return 0;return 1ll*fac[a]*finv[b]%p*finv[a-b]%p;
}
void solve(ll id){n=read(),k=read(),p=1e9+7;cout<<"Case #"<<id<<": ";if(n==2){if(k==1) puts("1");else puts("0");return;}init();ll res=0;for(ll t=k;t<=n/2;t++){ll coef=1;if((t-k)%2==1) coef=p-1;ll cur=1ll*C(t,k)*C(n,2*t)%p*ffac[2*t-1]%p*ffac[2*n-2*t-3]%p*ffinv[2*n-3]%p;cur=1ll*cur*coef%p;res+=cur,res%=p;}printf("%lld\n",res);
}
int main(){ll T=read();ll id=0;while(T--){id++;solve(id);}return 0;
}