luoguP3321 [SDOI2015]序列统计

luoguP3321 [SDOI2015]序列统计

原题传送门:>Here<

定义$f$为$S$的生成函数。

则答案为

$$f^n_x$$

其中多项式卷积定义为

$$
(fg)k=\sum{ij\equiv k(mod M)}f_ig_j
$$

这个卷积比较难做。

我们发现出题人给了一个性质:$M$为质数。因此$M$必定有原根。

所以$1\cdots M-1$中的每一个数都可以被表示为原根的整次幂。

我们定义

$$g^{a_i}=i$$

$$f’i=f{a_i}$$

则卷积就变成

$$
{(f*g)k=\sum{i+j\equiv k(mod M)}f_ig_j}
$$

答案就变成
$$
{f’}^n_{a_x}
$$

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long long


int n,m,P=1004535809,x,len,mg,loga[8001],tem1[32001],tem2[32001],t1[32001],t2[32001],Lim=1,L=-1,R[32001],inv;
int invg,may[1010],top;
int qsm(int a,int b,int P=1004535809){
int ans=1;
while(b){
if(b&1)ans=(ans*a)%P;
a=(a*a)%P;
b>>=1;
}
return ans;
}
int get_g(int p){
int x=p-1;
for(int i=2;i*i<=x;++i)
if(!(x%i)){
may[++top]=(p-1)/i;
while(!(x%i)) x/=i;
}
if(x>1)may[++top]=(p-1)/x;

int y;
for(int i=2;;++i){
for(int j=1;y=may[j];++j)
if(qsm(i,y,p)==1) break;
if(!y) return i;
}
}
void NTT(int *a,int flag){
for(int i=0;i<Lim;i++)if(i<R[i])std::swap(a[i],a[R[i]]);
for(int i=1;i<Lim;i<<=1)
for(int j=0,T=qsm(flag,(P-1)/(i<<1));j<Lim;j+=(i<<1))
for(int k=0,t=1;k<i;k++,t=t*T%P){
int Nx=a[j+k],Ny=a[i+j+k]*t%P;
a[j+k]=(Nx+Ny)%P;
a[i+j+k]=(Nx-Ny+P)%P;
}
}
signed main(){
scanf("%lld%lld%lld%lld",&n,&m,&x,&len);
mg=get_g(m);
for(int i=1,last=1;i<m-1;i++)loga[(last*=mg)%=m]=i;
for(int i=1,tem;i<=len;i++){
scanf("%lld",&tem);
if(tem)tem1[loga[tem]]=1;
}
tem2[0]=1;

while(Lim<(m<<1))Lim<<=1,++L;
for(int i=0;i<Lim;i++)R[i]=(R[i>>1]>>1)|((i&1)<<L);
inv=qsm(Lim,P-2);

while(n){
NTT(tem1,3);
if(n&1){
NTT(tem2,3);
for(int i=0;i<Lim;i++)(tem2[i]*=tem1[i])%=P;
NTT(tem2,334845270);
for(int i=0;i<Lim;i++)(tem2[i]*=inv)%=P;
for(int i=Lim-1;i>=m-1;i--)(tem2[i-m+1]+=tem2[i])%=P,tem2[i]=0;
}
for(int i=0;i<Lim;i++)(tem1[i]*=tem1[i])%=P;
NTT(tem1,334845270);
for(int i=0;i<Lim;i++)(tem1[i]*=inv)%=P;
for(int i=Lim-1;i>=m-1;i--)(tem1[i-m+1]+=tem1[i])%=P,tem1[i]=0;
n>>=1;

}
printf("%lld",tem2[loga[x]]);
}
# NTT

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×