树上连通块的 dp 技巧 + 奇怪的组合数取模.
“点数减边数”
对于树上满足某种性质 $P$ 的连通块计数,有一个巧妙的转化 “点数减边数” .
枚举树上的每个点 $x$ ,计算出包含 $x$ ,且满足性质 $P$ 的连通块数目,对所有 $x$ 求和得到 $a$ .
再枚举树上每条边 $(x,y)$ ,计算出同时包含 $x,y$ ,且满足性质 $P$ 的连通块数目,对所有 $(x,y)$ 求和得到 $b$ .
每个连通块对 $a$ 贡献是点数,对 $b$ 贡献是边数,而树上的连通块也是一棵树,点数 = 边数 + 1.
于是可以得出满足性质 $P$ 的连通块数目就是 $a-b$ .
这种转化常用于求若干连通块的交,因为这样转化就变成了每个连通块都包含枚举的点/边,连通块之间就独立了.
计算完美集合数目
这道题就可以使用上面这个转化,计算选出能被 $x$ 测试的完美集合方案,减去能被 $x,y$ 同时测试的完美集合方案.
集合内肯定不能包含 $dist*v>Max$ 的点,可以将它们去掉,对剩下的点做一个背包,维护最优解和最优解的数目.
树上背包可以按照 dfs 序转移,若选了 $i$ ,则考虑其子树,转移到 $f_{dfn(i)+1}$ ,否则跳过其子树,转移到 $f_{dfn(i)+siz(i)}$ .
于是我们可以在 $O(nm)$ 的时间复杂度内求出能被某一个点或某两个点同时测试的完美集合数目.
计算模意义下组合数
如果没有再从集合中选出 $k$ 个的要求和 $5^{23}$ 这个奇怪的模数,这道题就已经优美地结束了.
出题人为了加大力度,还需要我们计算出 $\binom{s}{k}\bmod 5^{23}$ ,其中 $s$ 是计算出的集合数目,可以达到 $2^{60}$ , $k$ 可以达到 $10^9$ .
用拓展 Lucas 的思路,其实就是要设法算出 $p!$ 中含有的因子 $5$ 的个数以及 $\prod_{i\le p}[i\bmod 5\neq 0] i$ 的值.
前者可以直接 $O(\log p)$ 计算,关键在于如何计算后者.
在拓展 Lucas 中,我们是 $O(mod)$ 暴力算出一个循环节的贡献,但这里 $mod=5^{23}$ ,显然行不通.
考虑构造多项式 $F_p(x)=\prod_{1\le i\le p} [i\bmod 5\neq 0] (x+i)$ ,要求的答案就是这个多项式展开后的常数项.
若 $p$ 不是 $10$ 的整数倍,就先将最后不超过 $9$ 个一次式的乘积暴力乘出来,就可以将 $p$ 凑成 $10k$ 的形式.
考虑 $F_{10k}(x)=F_{5k}(x)\cdot F_{5k}(x+5k)$ ,其中 $F_{5k}$ 的常数项可以递归下去算.
而 $F_{5k}(x+5k)$ 在模 $5^{23}$ 下可以表示成一个关于 $(x+5k)$ 的多项式,形如 $\sum c_i\cdot (x+5k)^i$ .
而我们只关心展开后不含 $x$ 的常数项,可以发现当 $i\ge 23$ 时, 将 $(x+5k)^i$ 展开后常数项都为 $0$ ,没有贡献.
那么递归求出 $F_{5k}$ 展开后的前 $23$ 项,将 $(x+5k)^i$ 代入,展开后即可求得 $F_{5k}(x+5k)$ 的前 $23$ 项.
再暴力卷积合并得到 $F_{10k}$ 的前 $23$ 项,这样只会需要求 $O(\log s)$ 个 $F_{5k}$ 的前 $23$ 项,复杂度可以接受.
1 | //%std |