P6811「MCOI-02」Build Battle 建筑大师 魔怔题解

· · 题解

这是一篇不需要容斥，不需要注意力，不需要猜结论，不需要组合意义的题解！！1

考虑计算本质不同子序列的经典 DP。本题中，即为 f_i=2f_{i-1}-f_{i-m-1}，意为考虑前 i 个数的本质不同子序列均可以通过前 i-1 个数的答案决策是否拼上 a_i = i \bmod m + 1 得到，同时减去算重的（这部分均可通过 i-m-1 的答案拼上 a_i 得到）。边界是 f_0=1。

直接启动 GF。

令 F(x)=\sum_{i\ge 0}f_ix^i，则根据上述递推式有：

F(x) = 2xF(x)-x^{m+1}F(x)+1

解方程，有：

F(x) = \frac{1}{1-2x+x^{m+1}}

使用牛顿二项式定理提取系数：

\begin{aligned} \text{Ans} &= [x^n]F(x) \\ &= [x^n]\sum_{i\ge 0}\binom{-1}{i}(x^{m+1}-2x)^i \\ &= [x^n]\sum_{i\ge 0}(-1)^i\sum_{j=0}^i \binom{i}{j}x^{(m+1)j+(i-j)}(-2)^{i-j} \\ &= [x^n]\sum_{i \ge 0}(-1)^i\sum_{j=0}^ix^{mj+i}(-2)^{i-j}\binom{i}{j} \\ \end{aligned}

我们直接枚举 j，i 可以算出来。注意要保证 i \ge j。

\begin{aligned} \text{Ans} &= \sum_{j=0}^{\lfloor\frac{n}{m+1}\rfloor}(-1)^{n-mj}(-2)^{n-mj-j}\binom{n-mj}{j} \\ &= \sum_{j=0}^{\lfloor\frac{n}{m+1}\rfloor}(-1)^{j}2^{n-mj-j}\binom{n-mj}{j} \end{aligned}

显然对于 m 从 1 到 n，\lfloor\frac{n}{m+1}\rfloor 之和是 O(n \ln n) 量级的，直接计算即可。

以上。