洛谷P3321 [SDOI2015]序列统计

题目大意

有一个集合$S$，$S$中分元素都是在$0$到$m-1$之间的整数。给你一个整数$x\in [1,m-1]$，求有多少个长度为$n$的序列$A$，满足

$$\prod _{i=1}^n{A}_i=x(\mathrm{mod}m)$$

$1\le n\le 10^9,3\le m\le 8000,1\le x<m$

$m$为质数，保证$S$中的元素不重复。

题解

前置知识：

• 离散对数
• 快速数论变换（$NTT$）

将集合$S$中的每个元素和$x$都取离散对数，那么原问题就变为取$n$个数，使得

$$\sum _{i=1}^n{\text{Ind}}_g(A_i)={\text{Ind}}_g(x)(\mathrm{mod}\varphi (m))$$

因为$m$比较小，所以可以$O(m^2)$求原根。

因为$m$为质数，所以$\varphi (m)=m-1$。

用生成函数$G(x)$表示每个值的个数，则

$$G(x)=\sum _{i\in S}{x}^{{\text{Ind}}_g(i)}$$

那么取$n$次数后的生成函数可表示为

$$F(x)=[G(x){]}^n$$

那么答案就为所有次数为${\text{Ind}}_g(x)$（此处的$x$为题目中的$x$）的项数的系数之和。

用$NTT$优化多项式乘法，用快速幂求多项式的幂即可。

时间复杂度为$O(m^2+nm\log n)$。

code

#include<bits/stdc++.h>
using namespace std;
int s1,s[10005],ind[10005];
long long w,wn,f[50005],g[50005],a1[50005],a2[50005];
const long long G=3,mod=1004535809;
long long mi(long long t,long long v){if(!v) return 1;long long re=mi(t,v/2);re=re*re%mod;if(v&1) re=re*t%mod;return re;
}
void ch(long long *a,int l){for(int i=1,j=l/2;i<l-1;i++){if(i<j) swap(a[i],a[j]);int k=l/2;while(j>=k){j-=k;k>>=1;}j+=k;}
}
void ntt(long long *a,int l,int fl){for(int i=2;i<=l;i<<=1){if(fl==1) wn=mi(G,(mod-1)/i);else wn=mi(G,mod-1-(mod-1)/i);for(int j=0;j<l;j+=i){w=1;for(int k=j;k<j+i/2;k++,w=w*wn%mod){long long t=a[k],u=w*a[k+i/2]%mod;a[k]=(t+u)%mod;a[k+i/2]=(t-u+mod)%mod;}}}if(fl==-1){long long ny=mi(l,mod-2);for(int i=0;i<l;i++) a[i]=a[i]*ny%mod;}
}
void dd(long long *v1,long long *v2,int l){int len=1;while(len<2*l) len<<=1;for(int i=0;i<l;i++){a1[i]=v1[i];a2[i]=v2[i];}for(int i=l;i<len;i++) a1[i]=a2[i]=0;ch(a1,len);ch(a2,len);ntt(a1,len,1);ntt(a2,len,1);for(int i=0;i<len;i++) a1[i]=a1[i]*a2[i]%mod;ch(a1,len);ntt(a1,len,-1);for(int i=0;i<len;i++) v1[i]=0;for(int i=0;i<len;i++) v1[i%(l-1)]=(v1[i%(l-1)]+a1[i])%mod;
}
int find(int e){for(int i=2;i<=e;i++){for(int j=1,l=i;j<=e;j++,l=l*i%e){if(l==1){if(j==e-1) return i;break;}}}
}
void ksm(int t,int l){for(;t;t>>=1){if(t&1) dd(f,g,l);dd(g,g,l);}
}
int main()
{int n,m,x;scanf("%d%d%d%d",&n,&m,&x,&s1);int gt=find(m);for(int i=0,l=1;i<m-1;i++){ind[l]=i;l=l*gt%m;}for(int i=1;i<=s1;i++){scanf("%d",&s[i]);if(s[i]==0){--i;--s1;continue;}s[i]=ind[s[i]];++g[s[i]];}f[0]=1;ksm(n,m);printf("%lld",f[ind[x]]);return 0;
}