当前位置: 首页 > news >正文

【题解】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;
}
http://www.hskmm.com/?act=detail&tid=27654

相关文章:

  • ysyx:pa3.1批处理系统
  • C 语言的验证码图像识别系统实现
  • Nginx典型流控配置示例
  • 基于 C 语言的验证码图像识别系统实现
  • oppoR9m刷Linux系统: 引导知识
  • 操作系统知识点
  • JAVA: Mybatis添加xml执行多行更新语句时报错
  • 安装Docker(CentOS安装Docker,CentOS7安装DockerCompose,Docker镜像仓库) - a
  • 上代码演示下Profile-Guided Optimization (PGO)
  • 所有文档每页的第一行居中对齐
  • 109
  • 一个有趣的网站,可以给自己生成一个奖牌:aitokenawards.com
  • 20232416 2025-2026-1《网络与系统攻防技术》实验一实验报告
  • day008
  • lzr 的区间(interval)
  • IRB-120机械臂socket通信接受上位机指令运行程序段
  • 1.1.1.1 金融市场的定义与功能
  • 使用c#操作elasticsearch8
  • CF45C Dancing Lessons 题解
  • APUE学习笔记之文件IO(三) - Invinc
  • note
  • 供应链优化技术助力应对疫情挑战
  • 搜索关键词 - 呓语
  • 阅读《构建之法》产生的问题
  • 每日反思
  • 每日反思(2025.10.09)
  • 软件工程学习日志2025.10.9
  • 骄傲 雨伞边缘处的暗槽 从最原初裂缝开凿 被碰触和温暖击倒 停止思考
  • 1.1.1.2 直接融资vs间接融资的区别
  • 柳高国庆小小说创作比赛的构思和成文(未完成)