BZOJ4178 - A

今天模拟赛的第一题, NTT 作多项式乘法,把后面的转移快速幂一下就过了。需要注意的是 950009857 的原根是 7 而不是 3 。

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
// =================================
// author: memset0
// date: 2019.01.07 08:16:44
// website: https://memset0.cn/
// =================================
#include <bits/stdc++.h>
#define ll long long
namespace ringo {
template <class T> inline void read(T &x) {
x = 0; register char c = getchar(); register bool f = 0;
while (!isdigit(c)) f ^= c == '-', c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
if (f) x = -x;
}
template <class T> inline void print(T x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) print(x / 10);
putchar('0' + x % 10);
}
template <class T> inline void print(T x, char c) { print(x), putchar(c); }

const int N = 1e4 + 10, mod = 950009857;
int n, m, k, x;

int inv(int x) { return !x || x == 1 ? 1 : (ll)(mod - mod / x) * inv(mod % x) % mod; }
inline int fpow(int a, int b) {
int s = 1;
for (; b; b >>= 1, a = (ll)a * a % mod)
if (b & 1) s = (ll)s * a % mod;
return s;
}

typedef std::vector <int> vector;
std::vector <int> a, b;
int _a[N << 2], _b[N << 2], rev[N << 2], g[2][30];

inline void print(const vector &a) {
for (int i = 0, lim = a.size(); i < lim; i++)
print(a[i], " \n"[i == lim - 1]);
}

inline void ntt(int *a, int lim, bool flag) {
for (int i = 0; i < lim; i++) if (i < rev[i]) std::swap(a[i], a[rev[i]]);
for (int len = 1, cnt = 1; len < lim; len <<= 1, ++cnt)
for (int i = 0, wn = g[flag][cnt]; i < lim; i += (len << 1))
for (int j = 0, w = 1; j < len; j++, w = (ll)w * wn % mod) {
int x = a[i + j], y = (ll)w * a[i + j + len] % mod;
a[i + j] = (x + y) % mod, a[i + j + len] = (x - y + mod) % mod;
}
}

inline vector operator * (const vector &a, const vector &b) {
int lim = 1, k = 0, size_a = a.size(), size_b = b.size();
if (!size_a) return b;
if (!size_b) return a;
while (lim <= (size_a + size_b)) lim <<= 1, ++k;
for (int i = 0; i < size_a; i++) _a[i] = a[i];
for (int i = 0; i < size_b; i++) _b[i] = b[i];
for (int i = size_a; i < lim; i++) _a[i] = 0;
for (int i = size_b; i < lim; i++) _b[i] = 0;
for (int i = 0; i < lim; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (k - 1));
ntt(_a, lim, 0), ntt(_b, lim, 0);
for (int i = 0; i < lim; i++) _a[i] = (ll)_a[i] * _b[i] % mod;
ntt(_a, lim, 1), lim = inv(lim);
vector c(std::min(size_a + size_b - 1, n));
for (int i = 0; i < (int)c.size(); i++) c[i] = (ll)_a[i] * lim % mod;
return c;
}

void main() {
for (int i = 0; i < 30; i++) {
g[0][i] = fpow(7, (mod - 1) / (1 << i));
g[1][i] = fpow(fpow(7, mod - 2), (mod - 1) / (1 << i));
}
read(n), read(m), read(k);
for (int i = 1; i <= n; i++) read(x), a.push_back(x);
b.resize(n);
for (int i = 1; i <= m; i++) read(x), ++b[x];
for (; k; k >>= 1, b = b * b)
if (k & 1) a = a * b;
a.resize(n), print(a);
}

} signed main() { return ringo::main(), 0; }
Your browser is out-of-date!

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

×