题解 P3702 【[SDOI2017]序列计数】

· · 题解

快速幂

时隔一年，重新来看我的第一篇题解，简直惨不忍睹，当时连自己都没有完全理解就在写题解，现在重新水一发题解。

首先，考虑最简单的dp，用dp[k][i][j]表示当前枚举到第i位，当前数之和为j，k表示是否选择了质数，滚动数组滚掉i位，但是实际的复杂度为O(nm),能过多少分题面给的不清晰，反正至少能得到20分的好分数。

显然，这种是完全过不了的。但是当我们深入分析这个转移的实质，就会发现在每次往后一位转移的时候，转移是固定的，而我们用dp转移的时候会有大部分的重复，就显得很劣。

那么我们来重新考虑一下这个转移。(先不考虑质数的问题) 我们用f[i][j]表示在第i位选数和为j(在%p意义下的)，你会发现我这个和dp定义的没有什么区别。没错，我就是在废话。 对于最基础的转移，就是，f[i+1][j]= \sum_{(k+l)\%p==j} f[k]+1 ,推广一下就是f[i1+i2][j]+= \sum_{(k+l)\%p==j}f[i1][k]* f[i2][l] (定义为 f[i1]*f[i2] )。（记得mod 20170408） 对于这样一个式子，我们相当于f[i1],f[i2]，我们相当于重新定义了他们的乘法法则，那么我们就可以对他进行快速幂。 现在我们唯一的问题就是在于出现质数怎么办，其实很简单，我们定义f为取全部数的情况，g为只出现非质数的情况，那么对于最后的答案我们是不是用f-g就是的答案了。(因为最终和为p，那么答案记录在f[0]-g[0]中)。时间复杂度 O(p^2logn)，完全能通过此题。

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define inf 999999999
#define dl double
#define ll long long
#define re register
#define V inline void
#define LL inline ll
#define I inline int
#define B inline bool
#define FOR(i,a,b) for(re int i=(a) ,i##i=(b) ; i<=i##i ; ++i)
#define AFOR(i,a,b) for(re int i=(a) , i##i=(b) ; i>=i##i ; --i)
#define REP(i,u) for(re int i=head[u],v=edge[i].to;i!=-1;i=edge[i].nxt,v=edge[i].to)
#define gc (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin),fs==ft))?0:*fs++
// #define gc getchar()
using namespace std;
const int N=2e7+10,mo=20170408;
char buf[1<<18],*fs,*ft;
inline ll read() {
    ll w=0,p=0;
    char ch=gc;
    while(!isdigit(ch)) w=ch=='-'?1:0,ch=gc;
    while(isdigit(ch)) p=p*10+ch-'0',ch=gc;
    return w?-p:p;
}
inline void write(ll x) {
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
    return ;
}
int p,cnt,vis[N],pre[N];
ll n,m,f[300],g[300],F[300],G[300],c[300];
V mul(ll *a,ll *b){
    FOR(i,0,p-1) FOR(j,0,p-1) c[i+j]=(c[i+j]+a[i]*b[j])%mo;
    FOR(i,0,p-1) a[i]=(c[i]+c[i+p])%mo,c[i]=c[i+p]=0;
    return ;
}
int main(){
    n=read(),m=read(),p=read();
    f[1]=g[1]=F[0]=G[0]=1;
    FOR(i,2,m){
        ++f[i%p];
        if(!vis[i]) pre[++cnt]=i;
        else ++g[i%p];
        FOR(j,1,cnt){
            if(i*pre[j]>m) break;
            vis[i*pre[j]]=1;
            if(i%pre[j]==0) break;
        }
    }
    while(n){
        if(n&1) mul(F,f),mul(G,g);
        mul(f,f),mul(g,g),n>>=1;
    }
    write((F[0]-G[0]+mo)%mo);
    return 0;
}