题解 P2000 【拯救世界】

w36557658 · 2018-06-14 10:02:52 · 题解

欢迎访问我的博客：https://www.cnblogs.com/luyouqi233/p/9181680.html

看到这么多的限制条件，以及最后求方案数，很容易想到生成函数。

生成函数的讲解就请百度吧……以及下面公式的推导也不再阐述。

那我们就细致地列一下吧，从第一条限制到第十条限制依次如下：

1+x^6+x^{12}+\cdots=\frac{1}{1-x^6}

1+x+x^2+\cdots+x^9=\frac{1-x^{10}}{1-x}

1+x+x^2+\cdots+x^5=\frac{1-x^{6}}{1-x}

1+x^4+x^8+\cdots=\frac{1}{1-x^4}

1+x+x^2+\cdots+x^7=\frac{1-x^{8}}{1-x}

1+x^2+x^4+\cdots=\frac{1}{1-x^2}

1+x=\frac{1-x^{2}}{1-x}

1+x^8+x^{16}+\cdots=\frac{1}{1-x^8}

1+x^{10}+x^{20}+\cdots=\frac{1}{1-x^{10}}

1+x+x^2+x^3=\frac{1-x^{4}}{1-x}

接下来要做的就是把它们乘起来，得到\frac{1}{(1-x)^5}

将它展开成生成函数，则第n项系数，也就是答案，即为C_{n+5-1}^{5-1}=C_{n+4}^4高精度求出即可。