洛谷3321 [SDOI2015]序列统计

Luogu

LOJ

分析

考虑把乘积改为和怎么做。

考虑设一个数列 $S$ ,它的第 $i$ 项表示 $i$ 是否出现过。

设 $S$ 的生成函数为 $F(x)$ ,可以发现 $(F(x))^n$ 的第 $i$ 项表示 $i$ 的答案。

于是构造生成函数然后快速幂就好了。

但是这道题里是乘积,可以考虑求对数改乘为加。因为是模意义下,所以底数取原根即可。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=24000+10,M=8000+10;
const int mod=1004535809,G=3,invG=334845270;

int n,m,x,s;
int lg[M];
int F[N],ans[N],r[N];

inline int qpow(int a,int b,int mod) {
    int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod)
        if (b&1) c=1ll*c*a%mod;
    return c;
}

inline int getroot(int x) {
    static int fac[100]; int cnt=0;
    for (re int i=2,t=x-1;i<=t;++i) {
        if (t%i) continue;
        fac[++cnt]=i;
        while (t%i==0) t/=i;
    }
    for (re int g=2;;++g) {
        int flag=1;
        for (re int j=1;j<=cnt;++j)
            if (qpow(g,(x-1)/fac[j],x)==1) { flag=0; break; }
        if (flag) return g;
    }
}

inline void NTT(int* A,int n,int op) {
    for (re int i=0;i<n;++i) if (i<r[i]) swap(A[i],A[r[i]]);
    for (re int i=1;i<n;i<<=1) {
        int rot=qpow(op==1?G:invG,(mod-1)/(i<<1),mod);
        for (re int j=0;j<n;j+=(i<<1)) {
            int w=1;
            for (re int k=0;k<i;++k,w=1ll*w*rot%mod) {
                int x=A[j+k],y=1ll*w*A[j+k+i]%mod;
                A[j+k]=(x+y)%mod,A[j+k+i]=(x-y+mod)%mod;
            }
        }
    }
    if (op==-1) {
        int iv=qpow(n,mod-2,mod);
        for (re int i=0;i<n;++i) A[i]=1ll*A[i]*iv%mod;
    }
}

inline void Mul(int* A,int* B,int lim) {
    static int a[N],b[N];
    for (re int i=0;i<lim;++i) a[i]=A[i],b[i]=B[i];
    NTT(a,lim,1),NTT(b,lim,1);
    for (re int i=0;i<lim;++i) a[i]=1ll*a[i]*b[i]%mod;
    NTT(a,lim,-1);
    for (re int i=0;i<m-1;++i) A[i]=(a[i]+a[i+m-1])%mod;
    for (re int i=m-1;i<lim;++i) A[i]=0;
}

int main() {
    n=read(),m=read(),x=read(),s=read();
    int g=getroot(m);
    for (re int i=0;i<m-1;++i) lg[qpow(g,i,m)]=i;
    for (re int i=1;i<=s;++i) {
        int x=read()%m;
        if (x) ++F[lg[x]];
    }
    int lim=1,l=0;
    for (;lim<=m+m;lim<<=1,++l);
    for (re int i=0;i<lim;++i) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    ans[lg[1]]=1;
    for (;n;n>>=1,Mul(F,F,lim)) if (n&1) Mul(ans,F,lim);
    printf("%d\n",ans[lg[x]]);
    return 0;
}
最后修改:2019 年 09 月 27 日 01 : 18 PM

发表评论