纪念一下把 years C 性质场上打出来

· · 算法·理论

想公开在 luogu.com.cn，但是好像不能投稿题解，就投了算法·理论。

正文

不就是说恰好有一个强连通分量入度为 0 吗。

感觉先要推推强连通计数。主旋律半年前做过但是忘了，这下要做俯卧撑了。

记录一下 DP 值：f_S 表示 S 子图强连通方案数。

枚举入度为 0 的点？不知道。是不是和 DAG 计数挺像啊。f_S=\sum\limits_{T\subseteq S}(-1)^{|T|}E(S,S\backslash T)，唯一的区别是没限制 T\neq\emptyset？（E(S,T) 表示 S 往 T 指的边数，显然胡扯）

打个表看一下三个点的完全有向图。18 个强连通子图。推了推发现不一样，输。

嗯嗯，枚举一下入度为 0 的强连通分量。记一下 g_S 表示 S 分成一些强连通，奇正偶负？（此时，我已经和 zlt 的题解一模一样了）

然后因为算错导致算出来不是 18。我也不知道我怎么确信我算错了。然后开始暴力枚举 3 个点选强连通有那些情况。列出来搞一搞发现对了。当时真感觉轻松了许多！但是此时已经从开始思考 1h 多过去了。

转移很显然，先把 S 拆分的 g 转移掉（固定 lowbit 位在选定集合），f 也好转移了。然后再 g_s\gets g_s-f_s 即可。

可是怎么计算答案？一开始猜个 $-g_{2^n-1}$ 失败。发现两个点的完全图都输出 4！把每个 $f$ 代表的意义写出来再推到 $g$，发现对于两个孤立点的情况会被加两次，但只会被减一次。 好像每种情况都会被算一次，我成功使用 $O(n3^n)$ 的时间算出了 $2^{2m}$！不怪我 3 个点完全图输出的是 64！ 这下意识到两个孤立点被加两次，那减 2 倍不就行了。可以 $O(n^2)$ 的计算 $k_i$ 表示选 $i$ 个强连通的贡献系数。$k_1=1,k_i=-\sum\limits_{j<i}k_j\text{C}_{i}^j$。再 DP 一个 $h_{i,S}$ 表示把 $S$ 划成 $i$ 个强连通的方案数，转移固定 lowbit 显然。贡献是 $h_{i,S}k_i$，3 个点完全图输出 51，赢！乘上 $4^{-m}$，大样例启动！ 测一下 years2，后三个全没过，哦原来是我多测没清空。然后过了。把 years3 第一个点贺 5 遍（杭师大的 i3 上）跑了 2.8s，赢！本来以为要去掉 `#define int long long` 卡卡常，但是不用！总共用时：2h。 ### 花絮 赛后发现 $k_i=(-1)^{i+1}i$。也就是有 $\sum (-1)^{(i+1)}\text{C}_n^ii=[n=1]$。 搞点证明：$i\text{C}_n^i=n\text{C}_{n-1}^{i-1}$，原式容易变成 $n(x+1)^{n-1},x=-1$ 带入展开后的情形。也可以直接 $(x+1)^n$ 求导后看出。 糊了一个组合意义：$n$ 个人选一些委员和一个班长，奇正偶负。容易发现固定一个队长之后选某个人或不选是方案数一样的，抵消了。当 $n=1$ 时选不出另外一个人所以特殊。 不得不说，$i\text{C}_n^i=n\text{C}_{n-1}^{i-1}$ 有个组合意义是 $n$ 个人选 $i$ 个委员，其中有一名班长的方案数，两种方案的区别在于先选班长还是先选委员再选班长。 因为 $\sum(-1)^{i}\text{C}_{n}^i=[n=0]$ 有个代数意义是 $(x+1)^m,x=-1$，组合意义是选一些委员，奇正偶负。考虑某个人选或不选方案数是一样的。所以组合意义和吸收恒等式差不多？？？？？我感觉本质差不多吧。 （给 HL_Lee4974 看：$(x+1)^n,x=-1$ 求导！） （给 lqyc 看：首选肯定吸收）