CF1821F 题解

dAniel_lele · 2023-04-12 23:56:13 · 题解

考虑先选出 m 个长度为 k+1 的段作为树倒下的地方。每种倒下方法可以选开头和结尾，理应有 2^m 个位置可以放树。然而，不难发现如果两段之间距离大于等于 k 时后一段选择起点及前面 k 个点会有重复计算。考虑当且仅当两段之间距离小于 k 时后一段乘 2，否则乘 1（只计算最右端的点向前面倒）。

不难发现我们要求的就是对于每个 i，有 i 段距离大于等于 k 的方案数，记为 f_i。很难计算，考虑容斥，钦定某 i 段距离大于等于 k 的方案数，记为 g_i。g_i 是容易计算的，易知为 \binom{n-m\times k-i\times k}{m}\times\binom{m}{i}。不难发现对 g 做二项式反演即可得到 f_i。n\log n 多项式处理即可。

问题不大，我不会多项式。

考虑用 g_i 表示 f_i：f_i=\sum_{j=i}^mg_j(-1)^{j-i}\binom{i}{j}。

考虑用 f_i 表示答案：ans=\sum_{i=0}^mf_i2^{m-i}。

考虑用 g_i 表示答案：ans=\sum_{i=0}^m(\sum_{j=i}^mg_j(-1)^{j-i}\binom{j}{i})2^{m-i}。

交换顺序：ans=\sum_{j=0}^mg_j2^{m-j}(\sum_{i=0}^j(-1)^{j-i}2^{j-i}\binom{j}{i})。

将后面改成二项式展开形式：ans=\sum_{j=0}^mg_j2^{m-j}(-1)^j(\sum_{i=0}^j(-1)^{i}2^{j-i}\binom{j}{i})。

将二项式展开形式变成二项式幂形式：ans=\sum_{j=0}^mg_j2^{m-j}(-1)^j(-1+2)^j。

最终得到：ans=\sum_{i=0}^m\binom{n-m\times k-i\times k}{m}\binom{m}{i}2^{m-i}(-1)^i。