P3702 [SDOI2017] 序列计数

题目描述

Alice 想要得到一个长度为 $n$ 的序列，序列中的数都是不超过 $m$ 的正整数，而且这 $n$ 个数的和是 $p$ 的倍数。

Alice 还希望，这 $n$ 个数中，至少有一个数是质数。

Alice 想知道，有多少个序列满足她的要求。

输入格式

一行三个数，$n,m,p$。

输出格式

一行一个数，满足 Alice 的要求的序列数量，答案对 $20170408$ 取模。

输入输出样例 #1

输入 #1

3 5 3

输出 #1

33

说明/提示

对 $20\mathrm{\%}$ 的数据，$1\le n,m\le 100$。

对 $50\mathrm{\%}$ 的数据，$1\le m\le 100$。

对 $80\mathrm{\%}$ 的数据，$1\le m\le {10}^6$。

对 $100\mathrm{\%}$ 的数据，$1\le n\le {10}^9,1\le m\le 2\times {10}^7,1\le p\le 100$。

题解

一道生成函数练手题。当然你也可以使用动态规划或其他计数方法来做。

对于“至少有一个数是质数”这一限制，我们考虑补集转化，即用全部方案减去不含任何质数的方案。

发现 $p$ 的数据范围相当小，我们希望能在 $\mathrm{mod}p$ 的同余系下进行计数。

定义多项式 $f_k(x)$，其中 $x^i$ 的系数 $a_i$ 为长度为 $k$ 的序列且和 $\mathrm{mod}p$ 为 $i$ 的方案数。

利用生成函数卷积，则有：

$$f_{k+m}(x)=f_k(x)\times f_m(x)$$

我们只要先构造出 $f_1(x)$，再求出其 $n$ 次方即可得到想要的答案。