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)

量级的，直接计算即可。

以上。

文章操作