SDOI2017序列计数

蒟蒻来水题啦......

转移方程：dp[i][j]=∑dp[i−1][(j−k)modp] i表示到第i个位置，j表示%p的余数，k表示枚举当前位置放的数1<=k<=m。

对于正常情况和一个质数都不用的分别算一下，减一下就好了，最后答案是dp[n][0]；

一看题发现似乎做过，然后就写了个朴素的O(n*p*m)，然后20分。

#include<stdio.h>
#include<string.h>
#define mo 20170408
int n,m,p,pri[2000005],pcont,dp[105][105],ans;
bool isnp[20000005];
void init();
int main()
{
    scanf("%d%d%d",&n,&m,&p);
    init(); int i,j,k,sb;
    for(i=1;i<=m;i++) dp[1][i%p]++;
    for(i=1;i<n;i++)
    {
        for(j=0;j<p;j++)
        {
            for(k=1;k<=m;k++)
            {
                sb = (j+k)%p;
                dp[i+1][sb] += dp[i][j];
                if(dp[i+1][sb]>=mo) dp[i+1][sb]%=mo;
            }
        }
    }
    ans = dp[i][0];
    memset(dp,0,sizeof(dp));
    for(i=1;i<=m;i++){if(isnp[i]) dp[1][i%p]++;}
    for(i=1;i<n;i++)
    {
        for(j=0;j<p;j++)
        {
            for(k=1;k<=m;k++)
            {
                if(isnp[k])
                {
                    sb = (j+k)%p;
                    dp[i+1][sb] += dp[i][j];
                    if(dp[i+1][sb]>=mo) dp[i+1][sb]%=mo;
                }
            }
        }
    }
    printf("%d",(ans-dp[i][0]+mo)%mo);
    return 0;
}
void init()
{
    int i,j; isnp[1] = true;
    for(i=2;i<=m;i++)
    {
        if(!isnp[i]) pri[++pcont] = i;
        for(j=1;j<=pcont;j++)
        {
            if(i*pri[j]>m) break;
            isnp[i*pri[j]] = true;
            if(i%pri[j]==0) break;
        }
    }
} 

然后打了个矩乘优化O（p*m），80分。

#include<stdio.h>
#include<string.h>
#define lll long long
#define mo 20170408
int n,m,p,pri[2000005],pcont,dp[105];
lll ans;
bool isnp[20000005];
void init();
struct mat
{
    lll ori[105][105];
    mat operator * (const mat &y) const
    {
        mat ret;
        int i,j,k;
        for(i=0;i<p;i++)
            for(j=0;j<p;j++)
            {
                ret.ori[i][j] = 0;
                for(k=0;k<p;k++)
                {
                    ret.ori[i][j] += (ori[i][k]*y.ori[k][j])%mo;
                    if(ret.ori[i][j]>=mo) ret.ori[i][j]%=mo;
                }
            }
        return ret;
    }
};
mat A,B;
mat ksm(mat,int);
void solve1();
void solve2();
int main()
{
    scanf("%d%d%d",&n,&m,&p);
    init(); solve1(); solve2();
    printf("%lld",ans);
    return 0;
}
void init()
{
    int i,j; isnp[1] = true;
    for(i=2;i<=m;i++)
    {
        if(!isnp[i]) pri[++pcont] = i;
        for(j=1;j<=pcont;j++)
        {
            if(i*pri[j]>m) break;
            isnp[i*pri[j]] = true;
            if(i%pri[j]==0) break;
        }
    }
} 
mat ksm(mat x,int n)
{
    mat ret = x; n--;
    while(n)
    {
        if(n&1) ret  = ret*x;
        x = x*x;
        n >>= 1;
    }
    return ret;
}
void solve1()
{
    int i,j;
    for(i=1;i<=m;i++) dp[i%p]++;
    for(i=0;i<p;i++)
        for(j=1;j<=m;j++)
            A.ori[((i-j)%p+p)%p][i]++;
    A = ksm(A,n-1);
    for(i=0;i<p;i++)
    {
        ans += dp[i]*A.ori[i][0]%mo;
        if(ans>=mo) ans %= mo;
    }
}
void solve2()
{
    memset(dp,0,sizeof(dp));
    int i,j;
    for(i=1;i<=m;i++){if(isnp[i]) dp[i%p]++;} 
    for(i=0;i<p;i++)
        for(j=1;j<=m;j++)
            if(isnp[j]){B.ori[((i-j)%p+p)%p][i]++;}
    B = ksm(B,n-1);
    lll ans1 = 0;
    for(i=0;i<p;i++)
    {
        ans1 += dp[i]*B.ori[i][0]%mo;
        if(ans1>=mo) ans1 %= mo;
    }
    ans = (ans-ans1+mo)%mo;
}

然后就不会了，查题解以后才知道构造矩阵还可以优化,第一次知道还可以这样，自己真是弱，感觉要挂。

#include<string.h>
#define lll long long
#define mo 20170408
int n,m,p,pri[2000005],pcont,dp[105];
lll ans;
bool isnp[20000005];
void init();
struct mat
{
    lll ori[105][105];
    mat operator * (const mat &y) const
    {
        mat ret;
        int i,j,k;
        for(i=0;i<p;i++)
            for(j=0;j<p;j++)
            {
                ret.ori[i][j] = 0;
                for(k=0;k<p;k++)
                {
                    ret.ori[i][j] += (ori[i][k]*y.ori[k][j])%mo;
                    if(ret.ori[i][j]>=mo) ret.ori[i][j]%=mo;
                }
            }
        return ret;
    }
    void show()
    {
        int i,j;
        for(i=0;i<p;i++)
        {
            for(j=0;j<p;j++) printf("%lld ",ori[i][j]);
            printf("
");
        }
    }
};
mat A,B;
mat ksm(mat,int);
void solve1();
void solve2();
int main()
{
    scanf("%d%d%d",&n,&m,&p);
    init(); solve1(); solve2();
    printf("%lld",ans);
    return 0;
}
void init()
{
    int i,j; isnp[1] = true;
    for(i=2;i<=m;i++)
    {
        if(!isnp[i]) pri[++pcont] = i;
        for(j=1;j<=pcont;j++)
        {
            if(i*pri[j]>m) break;
            isnp[i*pri[j]] = true;
            if(i%pri[j]==0) break;
        }
    }
} 
mat ksm(mat x,int n)
{
    mat ret = x; n--;
    while(n)
    {
        if(n&1) ret  = ret*x;
        x = x*x;
        n >>= 1;
    }
    return ret;
}
void solve1()
{
    int i,j;
    for(i=1;i<=m;i++) dp[i%p]++;
    for(i=1;i<=m;i++) A.ori[((-i)%p+p)%p][0]++;
    for (i=1;i<p;i++)
        for (j=0;j<p;j++)
            A.ori[j][i]=A.ori[(j-1+p)%p][i-1];
    //A.show();
    A = ksm(A,n-1);
    for(i=0;i<p;i++)
    {
        ans += dp[i]*A.ori[i][0]%mo;
        if(ans>=mo) ans %= mo;
    }
}
void solve2()
{
    memset(dp,0,sizeof(dp));
    int i,j;
    for(i=1;i<=m;i++){if(isnp[i]) dp[i%p]++;}
    for(i=1;i<=m;i++){if(isnp[i])B.ori[((-i)%p+p)%p][0]++;}
    for (i=1;i<p;i++)
        for (j=0;j<p;j++)
            B.ori[j][i]=B.ori[(j-1+p)%p][i-1];
    B = ksm(B,n-1);
    lll ans1 = 0;
    for(i=0;i<p;i++)
    {
        ans1 += dp[i]*B.ori[i][0]%mo;
        if(ans1>=mo) ans1 %= mo;
    }
    ans = (ans-ans1+mo)%mo;
}

话说第一次用取余构造矩阵，自己真是做题少。