LOJ #2183「SDOI2015」序列统计

有好多好玩的知识点

LOJ

题意：在集合中选$ n$个元素(可重复选)使得乘积模$ m$为$ x$，求方案数对$ 1004535809$取模

$ n<=10^9，m<=8000且是质数，集合大小不超过m$

$ Solution:$

我们先考虑改乘积为加和之后怎么做

直接对于集合中的数构建生成函数

所要求的就是这个生成函数的$ n$次幂的所有模$ m$为$ c$的项的系数的和

用快速幂优化这个生成函数的$ n$次幂

每次乘法之后立刻把$ [m,2m)$的系数加回$[0,m)$

这样可以保证每时每刻生成函数的长度不超过$ m$

就可以直接$ NTT$优化这个过程了

时间复杂度为$ O(m log m log n)$

然后考虑乘积的情况

我们知道$ x^ax^b=x^{a+b}$

尝试把每个数改成某个底数的若干次方

由于$ m$是质数一定存在原根

原根有性质是它的$[0,phi(m))$在模$ m$意义下互不相同

这样就可以直接把每个集合中的数改成$ m$的原根的若干次方就好了

然后就是加和情况的做法

复杂度不变

注意可能要特判原集合中存在$ 0$的情况

$ my \ code$

#include<ctime>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<queue>

#include<vector>

#define p 1004535809

#define rt register int

#define ll long long

using namespace std;

inline ll read(){

    ll x = ; char zf = ; char ch = getchar();

    while (ch != '-' && !isdigit(ch)) ch = getchar();

    if (ch == '-') zf = -, ch = getchar();

    while (isdigit(ch)) x = x *  + ch - '', ch = getchar(); return x * zf;

}

void write(ll y){if(y<)putchar('-'),y=-y;if(y>)write(y/);putchar(y%+);}

void writeln(const ll y){write(y);putchar('\n');}

int i,j,k,m,n,x,y,z,cnt,c,yg;

int a[],val[];

namespace NTT{

    int ksm(int x,int y){

        int ans=;

        for(rt i=y;i;i>>=,x=1ll*x*x%p)if(i&)ans=1ll*x*ans%p;

        return ans;

    }

    vector<int>R;

    void NTT(int n,vector<int>&A,int fla){

        A.resize(n);

        for(rt i=;i<n;i++)if(i>R[i])swap(A[i],A[R[i]]);

        for(rt i=;i<n;i<<=){

            int w=ksm(,(p-)//i);

            for(rt j=;j<n;j+=i<<){

                int K=;

                for(rt k=;k<i;k++,K=1ll*K*w%p){

                    const int x=A[j+k],y=1ll*K*A[i+j+k]%p;

                    A[j+k]=(x+y)%p,A[i+j+k]=(x-y)%p;

                }

            }

        }

        if(fla==-){

            reverse(A.begin()+,A.end());

            int invn=ksm(n,p-);

            for(rt i=;i<n;i++)A[i]=1ll*A[i]*invn%p;

        }

    }

    void mul(int del,int n,vector<int>&A){

        NTT(n,A,);

        for(rt i=;i<n;i++)A[i]=1ll*A[i]*A[i]%p;

        NTT(n,A,-);

        for(rt i=del;i<n;i++)(A[i%del]+=A[i])%=p,A[i]=;

    }

    void calc(int n,vector<int>&A,int y,int pl){

        int lim=;

        while(lim<=n*+)lim<<=;

        R.resize(lim);A.resize(lim);

        for(rt i=;i<lim;i++)R[i]=(R[i>>]>>)|((i&)*(lim>>));

        vector<int>ans;ans.resize(lim);

        ans[]=;

        for(rt i=y;i;i>>=,mul(n,lim,A))if(i&){

            NTT(lim,ans,);NTT(lim,A,);

            for(rt j=;j<lim;j++)ans[j]=1ll*ans[j]*A[j]%p;

            NTT(lim,ans,-);NTT(lim,A,-);

            for(rt j=n;j<lim;j++)(ans[j%n]+=ans[j])%=p,(A[j%n]+=A[j])%=p,ans[j]=,A[j]=;

        }

        writeln((ans[pl]+p)%p);

    }

};

vector<int>A,B;

using namespace NTT;

int main(){

    n=read();m=read();c=read();k=read();

    A.resize(m+);

    for(rt i=;i<=m;i++){

        for(rt j=,k=i;j<m-;j++,k=1ll*k*i%m)if(k==)goto GG;

        yg=i;break;

        GG:;

    }

    for(rt i=,j=;i<m-;i++,j=1ll*yg*j%m)val[j]=i;

    for(rt i=;i<=k;i++){

        x=read();if(x)A[val[x]]++;

    }

    calc(m-,A,n,val[c]);

    return ;

}

巴特西

LOJ #2183「SDOI2015」序列统计

最新文章

热门文章