原根与NTT在SDOI中不常见的露面

题目大意

集合\(S\)中选\(n\)次数, 乘积在\(mod \ M\)意义下为\(x\)的方案数.

解题报告

想办法把乘积转成和, 因为模的是一个质数, 而 \([1,M-1]\) 的每一个数都对应原根\(r\)的一个幂, 这样就成功的积化和了.

问题变为选\(n\)次数, 和为一个数的方案数, 这个用倍增+NTT随便搞搞就好了, 注意的一点是要做循环卷积, 因为下标是有模意义的.

吐槽自己的倍增不如快速幂快?

代码

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
119
#include <bits/stdc++.h>
using namespace std;
#define FORU(i, a, b) for (register int i = int(a), nn = int(b); i <= nn; ++i)
#define FORD(i, a, b) for (register int i = int(a), nn = int(b); i >= nn; --i)
#define REP(i, b) for (register int i = 0, nn = int(b); i < b; ++i)
#define DEBUG(x) cout << (#x) << " : " << x << endl
typedef long long ll;
typedef double ff;
const int p = 1004535809;
const int N = 1 << 14;
const int d = 3;
const int rd = 334845270;
int n, m, _m, _n, X, s, mir[N], re[N];
int a[N], f[N], _w[20], _rw[20], r, rn;
inline int fast(int x, int k) {
int ans = 1;
for (; k; k >>= 1, x=1LL*x*x%p)
if (k & 1) ans = 1LL*ans * x % p;
return ans;
}
inline void in(int &x) {
char ch = getchar();
for (; ch < '0' || ch > '9'; ch = getchar());
for (x=0; ch >= '0' && ch <= '9'; ch = getchar())
x = x * 10 + ch - 48;
}
inline void DFT(int *a, int f) {
for (register int i = 0; i < _n; ++i)
if (i < re[i]) swap(a[i], a[re[i]]);
register int wn, w, i, j, x, y, m, t;
for (m = 1, t=0; m < _n; m<<=1, ++t) {
wn = (f==1) ? _w[t] : _rw[t];
for (i = 0; i < _n; i += m<<1) {
w = 1;
for (j = 0; j < m; ++j) {
x = a[i+j], y = 1LL*a[i+j+m]*w%p;
a[i+j] = x+y, a[i+j+m] = x-y;
if (a[i+j] >= p) a[i+j] -= p;
if (a[i+j+m] < 0) a[i+j+m] += p;
w = 1LL*w * wn % p;
}
}
}
if (f == -1) for (register int i=0; i < _n; ++i)
a[i] = 1LL * a[i] * rn % p;
}
inline void one() {
DFT(f, 1);
for (register int i=0; i<_n; ++i)
f[i] = 1LL*f[i] * a[i] % p;
DFT(f, -1);
for (register int i=0; i<m-1; ++i) {
f[i] = f[i] + f[i+m-1], f[i+m-1]=0;
if (f[i] >= p) f[i] = f[i] - p;
}
}
inline void two() {
DFT(f, 1);
for (register int i=0; i<_n; ++i)
f[i] = 1LL*f[i] * f[i] % p;
DFT(f, -1);
for (register int i=0; i<m-1; ++i) {
f[i] = f[i] + f[i+m-1], f[i+m-1]=0;
if (f[i] >= p) f[i] = f[i] - p;
}
}
inline bool judge(register int x) {
memset(mir, -1, sizeof(mir));
for (register int i=1, ex=0; ex<m-1; i=i*x%m, ++ex) {
if (mir[i] != -1) return 0;
mir[i] = ex;
}
return 1;
}
int main() {
in(n), in(m), in(X), in(s);
for (r=2; !judge(r); ++r);
register int x, t=0;
for (register int i=1; i<=s; ++i) {
in(x); if (x) ++ a[mir[x]];
}
_n = 1, _m = (m-1) * 2;
while (_n < _m) _n <<= 1, ++t;
for (register int i=0, j=0; i<_n; ++i) {
re[i] = j;
for (register int k=_n>>1;(j^=k)<k;k>>=1);
}
rn = fast(_n, p-2), -- t;
_w[t] = fast(d, (p-1)/_n), _rw[t]=fast(rd, (p-1)/_n);
for (; t; --t)
_w[t-1]=1LL* _w[t] * _w[t] % p, _rw[t-1]=1LL*_rw[t]*_rw[t]%p;
f[0] = 1, DFT(a, 1);
for (register int i=1<<29,no=0; i; i>>=1) {
if (no) two();
if (i & n) one(), no |= 1;
}
printf("%d\n", f[ mir[X] ]);
return 0;
}

留言