P2000

Aryper · 2021-12-24 11:33:43 · 个人记录

拯救世界

在学校机房里看的。

比较适合作为生成函数的入门例题。

但是要写高精度，在学校里还是算了。

只讲一下思路。

根据题目所给的十个限制，我们其实可以列出十个生成函数：

F_1(x)=\sum_{n\ge 0}x^{6n}=\dfrac{1}{1-x^6}

F_2(x)=\sum_{n=0}^9x^n=\dfrac{1-x^{10}}{1-x}

F_3(x)=\sum_{n=0}^5x^n=\dfrac{1-x^6}{1-x}

F_4(x)=\sum_{n\ge 0}x^{4n}=\dfrac{1}{1-x^4}

F_5(x)=\sum_{n=0}^7x^n=\dfrac{1-x^8}{1-x}

G_1(x)=\sum_{n\ge 0}x^{2n}=\dfrac{1}{1-x^2}

G_2(x)=\sum_{n=0}^1x^n=\dfrac{1-x^2}{1-x}

G_3(x)=\sum_{n\ge0}x^{8n}=\dfrac{1}{1-x^8}

G_4(x)=\sum_{n\ge 0}x^{10n}=\dfrac{1}{1-x^{10}}

G_5(x)=\sum_{n=0}^3x^n=\dfrac{1-x^4}{1-x}

然后这个题的组合意义是什么？

用 n 块且满足条件，显然把 10 个生成函数乘起来，对于次数为 n 的项的系数就是答案（实质就是背包，不如说背包的实质其实是生成函数）。

不多做解释。

然后我们发现这个题最后乘下来的答案非常漂亮：

H(x)=\dfrac{1}{(1-x)^5}

这玩意是什么？

熟悉的人一眼就可以看出来，不做赘述。

H(x)=\sum_{n\ge 0}\dbinom{n+4}{n}x^n

第 n 项的系数就是 \dbinom{n+4}{n}=\dfrac{(n+1)(n+2)(n+3)(n+4)}{24}，就是答案。

但是这个题要高精度，而且要 NTT。。。。