题目描述
Alice 想要得到一个长度为 $n$ 的序列，序列中的数都是不超过 $m$ 的正整数，而且这 $n$ 个数的和是 $p$ 的倍数。
Alice 还希望，这 $n$ 个数中，至少有一个数是质数。
Alice 想知道，有多少个序列满足她的要求。
输入格式
一行三个数，$n,m,p$。
输出格式
一行一个数，满足 Alice 的要求的序列数量，答案对 $20170408$ 取模。
输入输出样例 #1
输入 #1
1 | |
输出 #1
1 | |
说明/提示
对 $20%$ 的数据，$1\leq n,m\leq100$。
对 $50%$ 的数据，$1\leq m \leq 100$。
对 $80%$ 的数据，$1\leq m\leq 10^6$。
对 $100%$ 的数据，$1\leq n \leq 10^9,1\leq m \leq 2\times 10^7,1\leq p\leq 100$。
题解
一道生成函数练手题。当然你也可以使用动态规划或其他计数方法来做。
对于“至少有一个数是质数”这一限制，我们考虑补集转化，即用全部方案减去不含任何质数的方案。
发现 $p$ 的数据范围相当小，我们希望能在 $\mod p$ 的同余系下进行计数。
定义多项式 $f_k(x)$，其中 $x^i$ 的系数 $a_i$ 为长度为 $k$ 的序列且和 $\mod p$ 为 $i$ 的方案数。
利用生成函数卷积，则有：
$$ f_{k+m}(x) = f_k(x) \times f_m(x) $$
我们只要先构造出 $f_1(x)$，再求出其 $n$ 次方即可得到想要的答案。
