做题记录 25.10.9

· · 个人记录

\purple\odot P11292 【MX-S6-T4】「KDOI-11」彩灯晚会

先通过组合意义转化为依次选择两条长度为 l 且颜色相同路径的方案数

枚举 c 表示两条链交的点数，令 g_c 表示恰好重合 c 个点的方案数，则答案为 \sum_c k^{n-2l+c+1}g_c

令 f_c 表示钦定重合 c 个点的方案数，则 f_c=\sum_{d=c}^l \binom dc g_d

二项式反演得

g_c=\sum_{d=c}^l \binom dc(-1)^{d-c} f_d

即答案为

&\sum_c k^{n-2l+c+1}g_c\\ =&\sum_c k^{n-2l+c+1}\sum_{d=c}^l \binom dc(-1)^{d-c} f_d\\ =&k^{n-2l+1}\sum_c k^c\sum_{d=c}^l \binom dc(-1)^{d-c} f_d\\ =&k^{n-2l+1}\sum_{d=0}^l f_d \sum_{c=0}^d \binom dck^c (-1)^{d-c} \\ =&k^{n-2l+1}\sum_{d=0}^l f_d (k-1)^d \\ \end{aligned}

令 g_{u,i,j} 表示选择两条链，长度分别为 i,j，钦定 c 个点相交的贡献系数为 (k-1)^c，两者结尾在 u 的方案数

令 f_{s,t,i} 表示 s 出发 t 结束经过 i 个点的方案数，令 st_{s,i}=\sum_t f_{s,t,i},to_{t,i}=\sum_s f_{s,t,i}

$$ g_{u,i,j}\gets to_{u,i} to_{u,j}(k-1)\\ g_{v,i+l,j+r}\gets g_{u,i,j} f_{u,v,l}f_{u,v,r} (k-1)\\ $$ 第二种可以分步转移 按照拓扑序转移，容易做到 $O(nml+n^2l^3)$，常数较小 [代码](https://www.luogu.com.cn/record/239583250) [参考](https://www.luogu.com.cn/article/mh28cwsf) # [QOJ #7419. Jiry Matchings](https://qoj.ac/problem/7419) $\quad$ [gym102331J](https://codeforces.com/gym/102331/problem/J) 对树轻重链剖分，令 $f_{u,0/1,i}$ 表示子树 $u$ 中 $u$ 本身是否匹配，选择 $i$ 对匹配，$u$ 为重链顶时考虑重儿子，否则不考虑重儿子 先考虑轻儿子，初始 $f_{u,0/1}$ 为空，考虑加入一个儿子 $v$，设 $u,v$ 之间连边为 $l

此时

f_{u,0,i+j}\gets f_{u,0,i}+\max(f_{v,0,j},f_{v,1,j})\\ f_{u,1,i+j+1}\gets f_{u,0,i}+f_{v,0,j}+l\\

然后考虑重链，设链从上往下为 p_{1\sim k},p_1=u，则 \forall v=p_i，有

f_{u,0,i+j}\gets f_{u,0,i}+\max(f_{v,0,j},f_{v,1,j})\\ f_{u,1,i+j}\gets f_{u,1,i}+\max(f_{v,0,j},f_{v,1,j})\\

特别地除了最后一个 p 外，设 v 连向下一个点的边权为 l，有

f_{u,1,i+j+1}\gets f_{u,0,i}+f_{v,0,j}+l\\

以上转移都是 (\max,+) 卷积，因此可以闵可夫斯基和优化

对 f 的影响可以视为矩乘，从而存在结合律，因此对于连续的求积，可以每次从一半的位置分治以保证复杂度

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

代码

参考