BZOJ[3992][SDOI2015]序列统计生成函数+NTT-白红宇

BZOJ[3992][SDOI2015]序列统计生成函数+NTT

阅读量：6713 次

发布时间：2019-06-25

本文共 1500 字，大约阅读时间需要 5 分钟。

首先了解一下

看我瞎bb也可以

因为原根\(g\)满足\(g^i,g^j(i,j\in (1,MOD-1),i\neq j)\)互不相同

则可以给每个数\(i\)定义一个指标\(ind_i\)表示模意义下的\(\log_g i\)，并且在区间\([1,\varphi(MOD)]\)中是互不相同的

和\(log\)类似，指标也满足\(ind_{i*j}\equiv ind_i+ind_j\)就可以把乘法弄成加法了

题目要求的\((a×b)mod M=x\)等价于\((ind[a]+ind[b])mod φ(M)=ind[x]\)

所以弄个生成函数再NTT，因为有取模，所以要在每次NTT后将\(\varphi(m)\)项后面的系数挪到前面，剩下的快速幂解决就好了

代码如下：

#include
    
     #include
     
      #include
      
       #include
       
        #define MOD 1004535809#define N 50020#define int long longusing namespace std;const bool DFT=false,IDFT=true;const int G=3;inline int read(){    int x=0,f=1;char c;    do c=getchar(),f=c=='-'?-1:f; while(!isdigit(c));    do x=(x<<1)+(x<<3)+c-'0',c=getchar(); while(isdigit(c));    return x*f;}typedef long long LL;void exgcd(LL a,LL b,LL &x,LL &y){    if(!b){        x=1;y=0;        return;    }    exgcd(b,a%b,y,x);    y=y-a/b*x;    return;}inline int GetNi(int k){    LL x,y;    exgcd(k,MOD,x,y);    return (x+MOD)%MOD;}inline int qpow(LL x,LL k,LL p){    LL sum;    for(sum=1;k;k>>=1,x=x*x%p)        if(k&1) sum=sum*x%p;    return sum;}bool b[N];int ind[N],pos[N],sum[N],p[N],q[N],a[N];int n,m,x,s,t,g,len,inv_len,inv_g;inline void NTT(int a[],bool mode){    for(int i=0;i
        
         >1]>>1;        if(i&1) pos[i]|=len>>1;    }    inv_len=GetNi(len);    sum[0]=1;    while(n){        if(n&1) Mul(sum,a,sum);        Mul(a,a,a);        n>>=1;    }    printf("%d",sum[ind[x]]);return 0;}