洛谷P3702 [SDOI2017]序列计数

题目大意：

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

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

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

对\(100\%\)的数据，\(1\leq n \leq 10^9,1\leq m \leq 2\times 10^7,1\leq p\leq 100\)

直接求不太好求，容斥一下，先求出全部的方案，再除掉没有质数的

全部的方案怎么求？

考虑\(dp\)，设\(f[i][j]\)表示\(i\)个数字，其和\(mod\ p\)为\(j\)的方案数，可以得到转移方程\(f[i_1+i_2][(j_1+j_2)\%p]=f[i_1][j_1]*f[i_2][j_2]\)

然后跑一年就出来了

考虑第一维，发现好像挺像个指数的运算

那我们把第一维用快速幂优化掉

当然我们要提前求出\(i=1\)时的\(f[i][j]\)，这个循环一遍就完了

设\(g[i][j]\)表示\(i\)个数字，其和\(mod\ p\)为\(j\)的且不含质数方案数，转移方程相同，只是初始的时候质数不贡献答案

然后就好了～

#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
    inline int read()
    {
        int x=0;char ch,f=1;
        for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
        if(ch=='-') f=0,ch=getchar();
        while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
        return f?x:-x;
    }
    const int N=2e7+10,p=20170408;
    int n,m,k;
    int f[233],g[233],F[233],G[233],c[233];
    signed prime[N>>1],num;
    bool vis[N];
    inline void work(int *a,int *b,int *d)
    {
        for(int i=0;i<k;++i)
        {
            for(int j=0;j<k;++j)
            {
                (c[i+j]+=a[i]*b[j])%=p;
            }
        }
        for(int i=0;i<k;++i)
        {
            d[i]=(c[i]+c[i+k])%p;
            c[i]=c[i+k]=0;
        }
    }
    inline void main()
    {
        n=read(),m=read(),k=read();
        f[1]=g[1]=F[0]=G[0]=1;
        for(int i=2;i<=m;++i)
        {
            ++f[i%k];
            if(!vis[i]) prime[++num]=i;
            else ++g[i%k];
            for(int j=1;j<=num;++j)
            {
                if(i*prime[j]>m) break;
                vis[i*prime[j]]=1;
                if(i%prime[j]==0) break;
            }
        }
        while(n)
        {
            if(n&1) work(F,f,F),work(G,g,G);
            work(f,f,f);
            work(g,g,g);
            n>>=1;
        }
        printf("%lld\n",(F[0]-G[0]+p)%p);
    }
}
signed main()
{
    red::main();
    return 0;
}

等等，我们发现了什么？

看这里

for(int i=0;i<k;++i)
{
    for(int j=0;j<k;++j)
    {
        (c[i+j]+=a[i]*b[j])%=p;
    }
}

一个卷积！在这里写个任意模数\(ntt\)岂不美哉

虽然对于这道题来说是没事找事

代码先鸽子了，毕竟我还不会任意模数\(ntt\)

洛谷P3702 [SDOI2017]序列计数

原文：https://www.cnblogs.com/knife-rose/p/12052451.html