[bzoj4818][Sdoi2017]序列计数

#include<iostream>
#include<cstdio>
#include<cstring>
#define mod 20170408
using namespace std;
inline int read()
{
    int x = 0; char ch = getchar();
    while(ch < ‘0‘ || ch > ‘9‘)ch = getchar();
    while(ch >= ‘0‘ && ch <= ‘9‘){x = x * 10 + ch - ‘0‘;ch = getchar();}
    return x;
}

int n,m,p,a[205],b[205],s[mod],num=0,c[205],d[205],C[205];
bool mark[mod];

void mul(int*A,int*B)
{
    memset(C,0,sizeof(C));
    for(register int i=0;i<p;i++)
        for(register int j=0;j<p;j++)
            C[i+j]=(C[i+j]+1LL*A[i]*B[j])%mod;
    for(int i=p-1;i>=0;i--) A[i]=C[i]+C[i+p];
}

int main()
{
    n=read();m=read();p=read();
    for(register int i=0;i<p;i++) a[i]=b[i]=m/p+(m%p>=i)-(i==0); 
    for(register int i=2;i<=m;i++)
    {
        if(!mark[i]) s[++num]=i,--b[i%p];
        for(register int j=1;s[j]*i<=m;j++)
        {
            mark[s[j]*i]=1;
            if(i%s[j]==0) break;
        }
    }
    for(c[0]=d[0]=1;n;n>>=1,mul(a,a),mul(b,b))
        if(n&1) mul(c,a),mul(d,b);
    printf("%d\n",(c[0]-d[0]+mod)%mod);
    return 0;
}