题解：P9357 「SiR-1」Lighthouse
yz_zy
·
·
题解
P9357 「SiR-1」Lighthouse
题意
其中，$n\le 1000$，$m\le 10^5$。
### 解
这个题，很好地锻炼了组合计数能力，我认为先推出多项式复杂度的第一步组合式子就很难了，相比而言求解的优化反而要更简单。
这个题给了我做计数题很好的启发，我们要去想好对什么计数，这个题很巧妙的地方就在于，它选择对一个操作 $(u,j)$ 计数，含义是对 $u$ 这个点，在点权为 $j$ 时操作了它，然后就去考虑它能产生的贡献。
枚举操作 $(u,j)$，考虑每一个点 $v$，如果其能够对 $(u,j)$ 造成贡献，就需要满足 $u$ 到 $v$ 路径上所有点权值都为 $j$，那么如果我们找到了所有的 $v$，也就相当于得到了 $u$ 的同点权联通块大小。
那么就只需计数 $v$ 的个数和我们操作 $(u,j)$ 的时刻 $i$ 即可，那么就可以得到初步的答案式子：
$$\operatorname{Ans}=\sum_{u=1}^n\sum_{v=1}^n\sum_{j=0}^{m-1}\sum_{i=0}^{m-1}\frac{(dj)!}{(j!)^d} {i\choose dj}(n-d)^{i-dj}n^{m-i-1}$$
$d$ 为 $u$ 到 $v$ 的节点个数。
这个式子的含义：
我们枚举操作 $(u,j)$ 的时刻是 $i+1$，
$\frac{(dj)!}{(j!)^d}：$ 我们这 $d$ 个点的操作顺序，每个点当前的点权为 $j$ 说明了总共操作了 $dj$ 次，然后因为是多重集排列数，所以方案要除以每种元素个数的阶乘，也就是这个。
${i\choose dj}：$ 前 $i$ 次操作里有 $dj$ 次操作动了这 $d$ 个点。
$(n-d)^{i-dj}：$ 这前 $i$ 次操作里，剩下的 $i-dj$ 次操作给了剩下的 $n-d$ 个点。
$n^{m-i-1}：$ 剩下的 $m-i-1$ 次操作，随便执行。
我们就通过这个手法将答案初步的式子推了出来，但是暴力地枚举 $u,v,i,j$ 复杂度是 $O(n^2m^2)$，直接做是肯定过不了的，考虑优化。
首先很明显的优化就是可以把 $u,v$ 去掉，只枚举 $d$ 就可以了，我们令 $\operatorname{cnt}_d$ 为树上距离为 $d$ 的点对个数，也就是：
$$\operatorname{cnt}_d=\sum_{u=1}^n\sum_{v=1}^n [\operatorname{dist}(u,v)=d]$$
因为 $n$ 很小，所以求这个不需要用点分治，直接暴力枚举即可，求 $cnt$ 复杂度是 $O(n^2)$。
那么答案就变成了：
$$\operatorname{Ans}=\sum_{d=1}^n\sum_{j=0}^{m-1}\sum_{i=0}^{m-1} \operatorname{cnt}_d \frac{(dj)!}{(j!)^d} {i\choose dj}(n-d)^{i-dj}n^{m-i-1}$$
现在的复杂度变成了 $O(nm^2)$，考虑枚举其中两个量来快速计算第三量，先把这个式子分离变量：
$$\operatorname{Ans}=n^{m-1}\sum_{d=1}^n \operatorname{cnt}_d\sum_{j=0}^{m-1}\frac{(dj)!}{(j!)^d (n-d)^{dj}}\sum_{i=0}^{m-1} {i\choose dj}\left(\frac{n-d}{n}\right)^i$$
然后，枚举 $d,j$，来想办法快速计算 $\sum_{i=0}^{m-1} {i\choose dj}\left(\frac{n-d}{n}\right)^i$。
我们考虑一个递推，一般看到这里都能想到递推来求解。
设，
$$f(x,y)=\sum_{i=0}^{m-1}{i\choose x}\left(\frac{n-y}{n}\right)^i$$
然后，利用帕斯卡公式分解开：
$$\begin{aligned}
f(x,y)&=\sum_{i=0}^{m-1}{i\choose x}\left(\frac{n-y}{n}\right)^i\\
&=\sum_{i=0}^{m-1} \left({i-1 \choose x-1}+{i-1\choose x}\right)\left(\frac{n-y}{n}\right)^i\\
&=\sum_{i=0}^{m-1} {i-1\choose x-1}\left(\frac{n-y}{n}\right)^i+\sum_{i=0}^{m-1}{i-1\choose x}\left(\frac{n-y}{n}\right)^i\\
&=\sum_{i=0}^{m-2} {i\choose x-1} \left(\frac{n-y}{n}\right)^{i+1}+\sum_{i=0}^{m-2}{i\choose x}\left(\frac{n-y}{n}\right)^{i+1}\\
&=\left(\frac{n-y}{n}\right) \left(f(x-1,y)-{m-1\choose x-1}\left(\frac{n-y}{n}\right)^{m-1}+f(x,y)-{m-1\choose x}\left(\frac{n-y}{n}\right)^{m-1}\right)\\
&=\frac{n-y}{n}f(x-1,y)+\frac{n-y}{n}f(x,y)-\left(\frac{n-y}{n}\right)^m\left({m-1\choose x-1}+{m-1\choose x}\right)
\end{aligned}$$
移项，合并同类项，逆用帕斯卡公式可以得到：
$$\frac{y}{n}f(x,y)=\frac{n-y}{n}f(x-1,y)-\left(\frac{n-y}{n}\right)^m{m\choose x}$$
最后再一整理可以得到：
$$f(x,y)=\frac{n-y}{y}f(x-1,y)-\frac{n}{y}\left(\frac{n-y}{n}\right)^m{m\choose x}$$
这样子这个就可以 $O(m)$ 递推了，这下枚举 $d,j$，然后推出所有的当前 $d$ 时的所有 $f$，再把答案式子写出：
$$\operatorname{Ans}=n^{m-1}\sum_{d=1}^n\operatorname{cnt}_d\sum_{j=0}^{m-1}\frac{(dj)!}{(j!)^d (n-d)^{dj}}\times f(dj,d)$$
但是要特殊注意的是当 $d=n$ 时，$n-d$ 为 $0$，需要单独提出来计算，快速幂什么的直接暴力计算即可，最后复杂度为 $O(nm+m\ln m)$。
很漂亮的一个题，很适合拿来练习组合计数。