P3702 [SDOI2017]序列计数

链接

分析：

　　首先可以容斥掉，用总的减去一个质数也没有的。

　　然后可以dp了，f[i][j]表示到第i个数，和在模p下是j的方案数，矩阵快速幂即可。

　　另一种方法：设T[1]是一个生成函数，为选了一个数，和在模p是多少的的方案数，那么T[1] * T[1] 即选了2个的方案数，这是一个卷积的形式，但是p特别小，直接暴力计算即可，然后外面套上快速幂。

代码：

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cmath>

#include<cctype>

#include<set>

#include<queue>

#include<vector>

#include<map>

using namespace std;

typedef long long LL;

inline int read() {

    int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

    for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

}

const int N = , mod = ;

int pri[N], n, m, p, tot;

bool nopri[N];

struct Poly{

    int a[];

    Poly() { memset(a, , sizeof(a)); }

}A, B;

Poly operator * (const Poly &A, const Poly &B) {

    Poly C;

    for (int i = ; i < p; ++i)

        for (int j = ; j < p; ++j)

            (C.a[(i + j) % p] += (1ll * A.a[i] * B.a[j]) % mod) %= mod;

    return C;

}

void init(int n) {

    nopri[] = true;

    for (int i = ; i <= n; ++i) {

        if (!nopri[i]) pri[++tot] = i;

        for (int j = ; j <= tot && pri[j] * i <= n; ++j) {

            nopri[i * pri[j]] = true;

            if (i % pri[j] == ) break;

        }

    }

}

Poly ksm(Poly A,int b) {

    Poly res = A; b --;

    while (b) {

        if (b & ) res = res * A;

        A = A * A;

        b >>= ;

    }

    return res;

}

int main() {

    n = read(), m = read(); p = read();

    init(m);

    for (int i = ; i <= m; ++i) {

        A.a[i % p] ++;

        if (nopri[i]) B.a[i % p] ++;

    }

    A = ksm(A, n); B = ksm(B, n);

    cout << (A.a[] - B.a[] + mod) % mod;

    return ;

}