BZOJ 3992 [SDOI2015]序列统计

题目链接：https://darkbzoj.tk/problem/3992

题意：略。

思路：考虑到 $P$ 是 $NTT$ 中经常使用的模数，我们不妨对式子两边取以 $P$ 的原根 $g$ 为底的对数，得到：

\log_{g}(x_{1}\times x_{2}\times x_{3}\times \cdots \times x_{n}) \equiv \log_{g}(X)(\bmod (P-1))

再得到

\log_{g}(x_{1})+\log_{g}(x_{2})+\cdots+\log_{g}(x_{n}) \equiv \log_{g}(X)(\bmod (P-1))

由此我们就可以把乘法变成了加法就可以构造生成函数来写，即

(a_{0}x^{0}+a_{2}x^{2}+\cdots+a_{m-2}x^{m-2})^{n}\bmod P

这里要用快速幂配合 $NTT$ 来求，最后要输出的就是 $X$ 的离散对数那一项的系数，然后这里还有要注意的是指数加起来 $\bmod (P-1)=ind[X]$ 的值, $ind[X]$ 代表 $X$ 的离散对数，所以我么要把 $i+P-1$ 那一项的系数也加到 $i$ 这一项的系数上来。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const int INF=0x3f3f3f3f;
const ll P=(479<<21)+1;
const ll MOD=P;
const ll N=(1<<18);
const double PI=acos(-1.0);
template<typename T> inline T gcd(T&a,T&b){return b==0?a:gcd(b,a%b);}
template<typename T> inline T lcm(T&a,T&b){return a/gcd(a,b)*b;}
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
int n,m,x,S;
int ind[maxn];
ll A[maxn],ans[maxn];
ll ksm(ll a,ll n,ll MOD){
    ll res=1;
    while (n){
        if (n&1) res=(res*a)%MOD;
        a=(a*a)%MOD;
        n>>=1;
    }
    return res;
}
ll PrimitiveRoot(ll p){
    if (p==2) return 1;
    for (ll g=2;g<p;g++){
        bool flag=true;
        ll m=sqrt(p+0.5);
        for (ll i=2;i<=m;i++) if ((p-1)%i==0){
            if (ksm(g,(p-1)/i,p)==1){
                flag=false;
                break;
            }
        }
        if (flag) return g;
    }
}
void iniInd(){
    int g=PrimitiveRoot(m),a=1;
    for (int i=0;i<m-1;i++,a=a*g%m) ind[a]=i;
}
struct NumberTheoreticTransfrom{
    int n,rev[maxn];
    ll g,C[maxn];

    void init(int m){
        n=1;
        while (n<m) n<<=1;
        int k=0;
        while ((1<<k)<n) k++;
        for (int i=0;i<n;i++){
            int t=0;
            for (int j=0;j<k;j++) if (i&(1<<j)) t|=(1<<(k-j-1));
            rev[i]=t;
        }
        g=3;
    }

    void NTT(ll* a,int DFT){
        for (int i=0;i<n;i++) if (i<rev[i]) swap(a[i],a[rev[i]]);
        for (int l=2;l<=n;l<<=1){
            int m=l>>1;
            ll wn=ksm(g,DFT==1?(P-1)/l:P-1-(P-1)/l,P);
            for (int k=0;k<n;k+=l){
                ll w=1LL;
                for (int j=0;j<m;j++){
                    ll u=w*a[k+j+m];
                    ll t=a[k+j];
                    a[k+j]=(t+u)%P;
                    a[k+j+m]=((t-u)%P+P)%P;
                    w=w*wn%P;
                }
            }
        }
        if (DFT==-1){
            ll inv=ksm(n,P-2,P);
            for (int i=0;i<n;i++) a[i]=a[i]*inv%P;
        }
        return;
    }

    void SQR(ll *A){
        NTT(A,1);
        for (int i=0;i<n;i++) A[i]=A[i]*A[i]%MOD;
        NTT(A,-1);
        for (int i=0;i<m-1;i++){
            A[i]=(A[i]+A[i+m-1])%MOD;
            A[i+m-1]=0;
        }
    }

    void mul(ll *A,ll* B){
        for (int i=0;i<n;i++) C[i]=B[i];
        NTT(A,1),NTT(C,1);
        for (int i=0;i<n;i++) A[i]=A[i]*C[i]%MOD;
        NTT(A,-1);
        for (int i=0;i<m-1;i++){
            A[i]=(A[i]+A[i+m-1])%MOD;
            A[i+m-1]=0;
        }
    }

    void powPoly(ll *A,int n,ll *ans){
        ans[0]=1;
        while (n){
            if (n&1) mul(ans,A);
            SQR(A);
            n>>=1;
        }
    }
}ntt;
int main(){
    read(n),read(m),read(x),read(S);
    ntt.init(m+m);
    iniInd();
    for (int i=1;i<=S;i++){
        int x;read(x);
        if (x) A[ind[x]]=1;
    }
    ntt.powPoly(A,n,ans);
    printf("%lld\n",ans[ind[x]]);
    return 0;
}

Written by Yiming Pan who lives and works in Hangzhou China. Welcome follow me on Github

Cannot load comments. Please check you network.