Week 4 计数

qoj8670 独立

最大独立集：类似定义 \(f_{u,0},f_{u,1},g_u=\max(f_{u,0},f_{u,1})\)，这里我们考虑设 \(\Delta_u=g_{u}-f_{u,0}\)，则有 \(g_u=\max(0,a_u-\sum_v \Delta_v)+\sum_v g_v\)。
故有最大独立集等于 \(\sum_u \max(0,a_u-\sum_v \Delta_v)\)。
由上式得 \(\Delta_u=\max(0,a_u-\sum_v \Delta_v)\)。
考虑 dp 出 \(f_{u,i=\Delta_u}\) 的方案数，这是一个儿子做卷积后枚举 \(a_u\) 转移。
设卷积数组是 \(g\)，则 \(\begin{cases}f_{u,i}=\sum_{i<a\le m} g_{a-i}&i>0\\ f_{u,0}=m^{siz_u}-\sum_{j>0}f_{u,j}&i=0 \end{cases}\)

\(\color{Red}\mathtt ?\) 可以证明，\(f_{u,i}\) 是一个 \(O(n)\) 次多项式的点值数组。
不妨设 \(k=n+\epsilon\)，那么可以求出 \(f_{u,1\sim k}\)，然后转移后我们求得的是 \(f_{u,m-k\sim m}\)，可以拉差求前 \(k\) 项。
最后答案为 \(\sum_{u,i} m^{n-siz_u}\times i\times f_{u,i}\)，这个也可以进行插值求答案。

上述的插值都可以使用 NTT 快速求出。

at_agc034_f [AGC034F] RNG and XOR

设 \(S=\sum_s p_sx^s\)，\(I=\sum_{s} x^s\)。
方程：\(FS+I-1-[x^0]FS=F\Rightarrow I-1-[x^0]FS=F(1-S)\)。
由于 \(\sum p_i=1\)，则 \(\sum [x^i]FS=\sum f_i\)，得到 \([x^0]FS=f_0+\sum_{i>0} f_i-[x^i]FS=f_0+2^{w}-1=2^w-1\)。
故 \(I-2^w=F(1-S)\)，这里是一个乘法逆。考虑乘法的过程反过来做，就是求点值后对位相除。但是这样除数可能是 0，就有点问题。

考虑 \(\mathtt{FWT}(I-2^w)_t=-[t>0]2^w\)。
注意到 \(\mathtt{FWT}(1-S)_0=1-\sum_{s} p_s=0\)。
第 0 位是 \(\frac{0}{0}\)，即 \(f_0\) 可以任意取。
而其他位由于一定存在一个解 \(f_t\)，故一定可以确定分母不是 0。
最后 IFWT 得到的 \(f_0\) 可能是错误的。由于是点值是 \(0\) 的地方出问题，那么就是全局偏移即可。

uoj310 【UNR #2】黎明前的巧克力

Deck-Building Game 双倍经验。

P11714 [清华集训 2014] 主旋律

设 \(f_s\) 表示子图 \(s\) 删边方案数，满足强连通。
考虑给图缩强连通，则 \(2^{\mathtt E(s)}=\sum_{t\subseteq s,t\ne \varnothing} h_t 2^{\mathtt E(s-t)+\mathtt E(t\to s-t)}\)。
然后 \(H=-\exp(-F+f_{\varnothing})\)。
这里可以从小到大解出 \(h_s\)，然后做集合幂级数 ln 即可。复杂度 \(O(3^n+2^nn^2)\)。

P10221 [省选联考 2024] 重塑时光

题意：
给出一些有向边，他们组成一个 DAG。等概率生成一个排列，并插入 \(k\) 个区分的分段点将排列划分为 \(k+1\) 个可以为空的连续段。
问是否可以重排连续段使得这是 DAG 的一个拓扑序。

把分段点用一个阶乘变成不区分的。
那么也就差不多是问，对于 \(i\le k\)，将图划分为 \(i\) 个大点，其中每个大点内部是一个拓扑序。然后大点组成的图是 DAG。
对于拓扑序，考虑每次增加一个节点到最后即可。
那么做 dp：\(f_{s,i}=\sum_{t\subseteq s,t\ne \varnothing}\sum_{1\le j\le i} g_{t,j}f_{s-t,i-j}\mathtt {NoEdge}(s\setminus t\to t)\)。
\(g\) 是划分大点的方案：\(f_s=\sum_{t\subseteq s,t\ne \varnothing} \mathtt{NoEdge}(t\leftrightarrow s\setminus t)g_{s-t}h_t\)
这里是一个卷积，由于次数不超过 \(k+1\)，那么可以转点值，最后插值。
复杂度 \(O(n3^n)\)。