「BZOJ3992」[SDOI2015]序列统计

Description

小C有一个集合SS,里面的元素都是小于MM的非负整数。他用程序编写了一个数列生成器,可以生成一个长度为NN的数列,数列中的每个数都属于集合SS。小C用这个生成器生成了许多这样的数列。但是小C有一个问题需要你的帮助:给定整数xx,求所有可以生成出的,且满足数列中所有数的乘积(modM)\pmod {M}的值等于xx的不同的数列的有多少个。小C认为,两个数列{Ai}\{A_i\}{Bi}\{B_i\}不同,当且仅当至少存在一个整数ii,满足AiBiA_i\neq B_i。另外,小C认为这个问题的答案可能很大,因此他只需要你帮助他求出答案(mod1004535809)\pmod{1004535809}的值就可以了。

Input

一行,四个整数,NNMMxxS|S|,其中S|S|为集合SS中元素个数。
第二行,S|S|个整数,表示集合S中的所有元素。
1N1091\leq N\leq 10^93M80003\leq M\leq 8000MM为质数
0xM10\leq x\leq M-1,输入数据保证集合S中元素不重复x[1,m1]x\in [1,m-1]
集合中的数[0,m1]\in [0,m-1]

Output

一行,一个整数,表示你求出的种类数(mod1004535809)\pmod{1004535809}的值。

Sample Input

1
2
4 3 1 2
1 2

Sample Output

1
8

Solution

fi,jf_{i,j}表示取到第ii个数,(modm)\pmod{m}结果为jj的方案数。
fi,j=xyj(modm)fi1,xfi1,yf_{i,j}=\sum _{x y\equiv j\pmod{m}}f_{i-1,x}f_{i-1,y}
X=loggx,Y=loggyX=\log_gx,Y=\log_gy,这里的ggmm的原根。
xxyy映射成XXYY
fi,jf_{i,j}表示取到第ii个数,(modm)\pmod{m}结果是ggjj次。
显然fi,j=X+Yj(modm1)fi1,xfi1,yf_{i,j}=\sum _{X+Y\equiv j\pmod{m-1}}f_{i-1,x}f_{i-1,y}
转移用NTTNTT优化。

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N =11000*2;
int n, m, x, tot;
const ll p = 1004535809;
int a[N];
int id[N], g;
int phi[N];
int b[N];
ll ksm(ll x, ll y, ll p) {
ll res = 1;
for(; y; y >>= 1, x = x * x %p)
if(y & 1) res = res * x % p;
return res;
}
int c[N];
int getroot() {
*b = 0;
phi[1] = 1;
for(int i = 2; i <= m; ++i) {
if(!phi[i]) phi[i] = i - 1, b[++*b] = i;
for(int j = 1; j <= *b && b[j] <= m / i; ++j) {
if(i % b[j] == 0) {
phi[i * b[j]] = phi[i] * b[j];
break;
}
else phi[i * b[j]] = phi[i] * phi[b[j]];
}
}
*c = 0;
for(int i = 1, x = phi[m]; i <= *b && x > 1; ++i) if(x % b[i] == 0){
c[++*c] = b[i];
while(x % b[i] == 0) x /= b[i];
}
for(int i = 2; i < m; ++i) {
bool fg = 1;
for(int j = 1; j <= *c; ++j)
if(ksm(i, phi[m] / c[j], m) == 1) {
fg = 0;
break;
}
if(fg) return i;
}
return 0;
}
ll f[N], tmp[N], res[N];
ll A[N], B[N], C[N], inv, inv2;
void NTT(ll *a, ll inv, int lim) {
if(lim == 1) return;
ll a1[N*2], a2[N*2];
for(int i = 0; i < lim; i += 2) {
a1[i >> 1] = a[i];
a2[i >> 1] = a[i + 1];
}
NTT(a1, inv, lim >> 1);
NTT(a2, inv, lim >> 1);
ll wn = ksm(inv, (p - 1) / lim, p), w = 1;
for(int i = 0; i < (lim >> 1); ++i, w = w * wn % p) {
a[i] = (a1[i] + w * a2[i] % p) % p;
a[i + (lim >> 1)] = (a1[i] - w * a2[i] % p + p) % p;
}
}
int lim;
void mul(ll *a, ll *b) {
memset(A,0,sizeof A);
memset(B,0,sizeof B);
memset(C,0,sizeof C);
for(int i = 0; i < m - 1; ++i) A[i] = a[i], B[i] = b[i];
NTT(A,3,lim);
NTT(B,3,lim);
for(int i = 0; i < lim; ++i)
C[i] = A[i] * B[i] % p;
NTT(C,inv,lim);
for(int i = 0; i < lim; ++i) C[i] = C[i] * inv2 % p;
for(int i = 0; i < m - 1; ++i) a[i] = (C[i] + C[i + m - 1]) % p;
}
int main() {
n = read(), m = read(), x = read(), tot = read();
for(int i = 1; i <= tot; ++i)
a[i] = read();
g = getroot();
inv = ksm(3, p - 2,p);

for(int i = 0; i < m - 1; ++i)
id[ksm(g, i, m)] = i;
lim = 1;
while(lim <= m * 2) lim <<= 1;
inv2 = ksm(lim, p - 2, p);
for(int i = 1; i <= tot; ++i) {
if(a[i])
++tmp[id[a[i]]];
}
res[id[1]] = 1;
for(; n; n >>= 1, mul(tmp, tmp)) {
if(n & 1)
mul(res, tmp);
}
writeln(res[id[x]]);
return 0;
}