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

「LG6596-How Many of Them」题解

P6596 How Many of Them

sol

首先发现 \(n\) 特别小(事实上不如题中给出的这么小。。),于是考虑枚举割边数量。

这么做的一个重要根据是存在如下结论:

对于一个 \(n\) 个点,已有 \(k\) 个联通块的图,记第 \(i\) 个联通块的点数为 \(a_i\),则连 \(k-1\) 条边使图联通的方案数为:

\[n^{k-2}\prod_{i=1}^ka_i \]

这个结论可以利用 prufer 序列证明。

因此我们关心的就是对于所有 \(k\in[0,m]\),存在 \(k\) 条割边的所有图形态 \(G\),下式的值:

\[\sum_G\prod_{i=1}^{k+1}a_i \]

考虑 DP,状态 \(f(i,j)\) 表示 \(i\) 个点 \(j\) 条割边上式的值,转移考虑枚举最后一个点 \(i\) 所在边双的状态,有:

\[f(i,j)=\sum_{k=1}^{i-1}\binom{i-1}{k-1}f(i-k,j-1)f(k,0) \]

\(k\) 为枚举的边双大小,转移式意义显然。

考虑边界条件,也就是 \(j=0\) 时的情况,其意义为 \(i\) 个点的图是一个边双的方案数,考虑容斥,用连通图方案数减去多个边双的方案数即可。多个边双的方案数显然可以通过已经求得的 \(f(i,j>0)\) 以及上面的结论得到,记 \(g(i)\)\(i\) 个点的连通图方案数,有转移式:

\[f(i,0)=\left(g(i)-\sum_{j=1}^{i-1}i^{j-1}f(i,j)\right)i \]

现考虑连通图方案数。同样考虑容斥,所有情况减去不连通的情况即可,同样的考虑枚举点 \(1\) 所在连通块状态,其余不相干的边任意连即可,有转移式:

\[g(i)=2^{\binom{i}{2}}-\sum_{j=1}^{i-1}\binom{i-1}{j-1}g(j)2^{\binom{i-j}{2}} \]

那么答案即为:

\[\sum_{i=0}^mn^{i-1}f(n,i) \]

实际实现上,为防止越界等各种意外情况,枚举上界不得超过 \(n-1\)

时间复杂度 \(O(n^2)\)

感觉还是比较适合入门的图计数(?),假如已知开头那个结论的话。其余各个部分都不要求特别有难度的算法,也没有很突兀的思维转折。

code

const int N=55;int n,m;
mint fc[N],iv[N];
mint f[N][N],g[N],ans;
#define C(n,m) (fc[n]*iv[m]*iv[(n)-(m)])inline void Main(){cin>>n>>m;fc[0]=1;rep(i,1,n)fc[i]=fc[i-1]*i;iv[n]=1/fc[n];per(i,n,1)iv[i-1]=iv[i]*i;g[1]=1;rep(i,2,n){g[i]=qpow(2,i*(i-1)/2);repl(j,1,i)g[i]-=C(i-1,j-1)*g[j]*qpow(2,(i-j)*(i-j-1)/2);}f[1][0]=1;rep(i,2,n){repl(j,1,i)repl(k,1,i)f[i][j]+=f[i-k][j-1]*C(i-1,k-1)*f[k][0];f[i][0]=g[i];repl(j,1,i)f[i][0]-=qpow(i,j-1)*f[i][j];f[i][0]*=i;}rep(i,0,min(m,n-1))ans+=qpow(n,i-1)*f[n][i];put(ans);
}
http://www.hskmm.com/?act=detail&tid=36057

相关文章:

  • 骗我呢
  • 手写体识别
  • 你好,我是肆闲:C语言的学习,成长与分享旅程
  • AGC 合集 1.0
  • 20231302邱之钊密码系统设计实验一第二
  • 深入BERT内核:用数学解密掩码语言模型的工作原理
  • ZR 2025 NOIP 二十连测 Day 6
  • 20251021
  • [论文笔记] Precision-Guided Context Sensitivity for Pointer Analysis
  • 英语_备忘_疑难
  • 数学题刷题记录(数学、数论、组合数学)
  • 朋友圈文案不会写?这个AI指令可能帮得上忙
  • 「JOISC2020-掃除」题解
  • 结对作业
  • CF简单构造小计
  • 深入认识ClassLoader - 一次投产失败的复盘
  • python 包来源镜像
  • CSharp基础复习-1
  • Linux7种文件类型
  • 米理 课程描述/学习计划/Study program
  • 2025年线路调压器厂家推荐榜:10kv线路调压器/单相线路调压器/三相线路调压器/助力电网稳定运行,优选品牌指南
  • Day15
  • 2025 智能/商超照明/灯具/灯光/源头厂家推荐榜:上海富明阳凭分区域光效领跑,生鲜 / 百货场景适配优选
  • 2025 艺考文化课推荐榜:济南震华学校 5 星领跑,全阶段体系适配基础补弱到高分冲刺
  • 2025 广州人力资源/派遣/劳务外包/人事代理/推荐榜:精典人才凭派遣合规 + 全场景适配领跑,企业用工优选
  • 2025 变电站厂家推荐榜最新资讯:撬装变电站/移动车载变电站/预制舱式变电站/移动变电站/预装式变电站/聚焦智能适配与可靠服务,这家企业成优选​
  • 题解:P12525 [Aboi Round 1] 私は雨
  • 完整教程:罗技G102有线鼠标自己维修教程
  • 挖矿-学校挖矿排查
  • 杂谈