题目分析

实际上两个人轮流取十分鸡肋,可以看作一个人取2t次。

考虑生成函数。

为了方便,我们对取的数向右偏移k位。

取2t次的生成函数为:
\[
F(x)=(\sum_{i=0}^{2k}x_i)^{2t}
\]

化一下式子:
\[
\begin{split}
F(x)&=(\frac{1-x^{2k+1}}{1-x})^{2t}\\
&=(1-x^{2k+1})^{2t}\cdot(1-x)^{-2t}
\end{split}
\]

对两个式子分别二项式展开:
\[
\begin{split}
F(x)&=\sum_{i=0}^{2t}(-1)^{2t-i}\binom{2t}{i}x^i\sum_j^{\infty}\binom{2t+j-1}{j}x^j
\end{split}
\]

我们对\(\sum_j^{\infty}\binom{2t+j-1}{j}x^j\)求一个前缀和,枚举i每次\(O(1)\)计算贡献即可。

时间复杂度\(O(kt)\)。

05-14 01:09