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 <algorithm>
#include <cstdio>
#define int long long
int mod;
// 这种写法我也第一次见，边写边学吧
// 直接不开在全局std里了，单独一个Math
namespace Math{
inline int qpow( int base , int p , const int mod ){
static int res;
for( res = 1 ; p ; p >>= 1 , base = base * base % mod )
if( p & 1 )
res = res * base % mod;
return res;
}
inline int inv( int x , const int mod ){
return qpow( x , mod-2 , mod );//费马小定理求逆元
}
}
const int mod1 = 998244353, mod2 = 1004535809, mod3 = 469762049, G = 3;
const int mod_1_2 = mod1 * mod2;
const int inv_1 = Math::inv(mod1, mod2), inv_2 = Math::inv(mod_1_2 % mod3, mod3);
struct Int{
int A , B , C;
// 空的默认构造函数
Int(){}
// 这个构造函数允许使用一个整数来初始化 A, B, C，它们都将被初始化为同一个值 __num
Int( int __num ): A(__num) , B(__num) , C(__num) {}
// 允许通过三个整数分别初始化 A, B, C
Int( int __A , int __B , int __C ): A(__A) , B(__B) , C(__C) {}
// 好神奇的操作，研究半天也没明白原理
// 只知道它可以做减法，出现负数就加上一个模数，只需要传入一个指针
static Int reduce( const Int & x ){
return Int( x.A + (x.A >> 31 & mod1) , x.B + (x.B >> 31 & mod2) , x.C + (x.C >> 31 & mod3) );
}
// 加减乘除的重载运算符，很精妙的写法
// 不太懂lhs和rhs是什么，只知道大概是两个input量，不像是数据结构里树的左孩子和右孩子
friend Int operator + ( const Int &lhs , const Int & rhs ){
return reduce(Int(lhs.A + rhs.A - mod1, lhs.B + rhs.B - mod2, lhs.C + rhs.C - mod3));
}
friend Int operator - ( const Int &lhs , const Int & rhs ){
return reduce(Int(lhs.A - rhs.A, lhs.B - rhs.B, lhs.C - rhs.C));
}
friend Int operator * ( const Int &lhs , const Int & rhs ){
return Int( lhs.A * rhs.A % mod1 , lhs.B * rhs.B % mod2 , lhs.C * rhs.C % mod3 );
}
int get(){
int x = (B - A + mod2) % mod2 * inv_1 % mod2 * mod1 + A;
return ((C - x % mod3 + mod3) % mod3 * inv_2 % mod3 * (mod_1_2 % mod) % mod + x) % mod;
}
};
#define maxn 200010 //maxn表示处理的最大元素数量
namespace Poly{
#define N (maxn << 1) //N 定义为 maxn 的两倍，表示用于 NTT 的数组大小。
/*
lim：表示当前处理的长度，是最小的2的幂大于等于输入大小的值
s：记录 lim 的二进制位数
rev：用于存储每个索引的反转（bit-reversal）值
Wn：预计算的旋转因子（根单位元），用于 NTT 计算
*/
int lim , s , rev[N];
Int Wn[N|1];
/*
初始化 NTT 相关参数
计算 lim 为不小于 n 的最小的2的幂
生成反转索引 rev，用于在 NTT 中重排数据
计算旋转因子 t，用于每个模数（mod1, mod2, mod3），通过幂函数 Math::pw 计算
初始化 Wn 数组，预计算旋转因子
*/
void init( int n ){
s = -1 , lim = 1;
while( lim < n ) lim <<= 1 , s ++;//填充
for(int i = 1;i < lim;i ++) rev[i] = rev[i >> 1] >> 1 | (i & 1) << s;
const Int t(Math::qpow(G, (mod1 - 1) / lim, mod1), Math::qpow(G, (mod2 - 1) / lim, mod2), Math::qpow(G, (mod3 - 1) / lim, mod3));
*Wn = Int(1);
for (Int *i = Wn; i != Wn + lim; ++i) *(i + 1) = *i * t;
}
/*
执行 NTT 转换；首先进行反转操作，将数组 A 中的元素按 rev 数组重排
进行蝶形操作（butterfly operation），对数组进行逐层计算，利用预计算的旋转因子 Wn
*/
inline void NTT(Int *A, const int op = 1) {
for (int i = 1; i < lim; ++i) if (i < rev[i]) std::swap(A[i], A[rev[i]]);
for (int mid = 1; mid < lim; mid <<= 1) {
const int t = lim / mid >> 1;
for (int i = 0; i < lim; i += mid << 1) {
for (int j = 0; j < mid; ++j) {
const Int W = op ? Wn[t * j] : Wn[lim - t * j];
const Int X = A[i + j], Y = A[i + j + mid] * W;
A[i + j] = X + Y, A[i + j + mid] = X - Y;
}
}
}
// 如果 op 为 0，表示是反向变换，则需要进行归一化，将结果除以 lim
if (!op) {
const Int ilim(Math::inv(lim, mod1), Math::inv(lim, mod2), Math::inv(lim, mod3));
for (Int *i = A; i != A + lim; ++i) *i = (*i) * ilim;
}
}
#undef N
}
int n , m , x;
Int A[maxn << 1], B[maxn << 1], C[maxn << 1];
signed main() {
scanf("%lld%lld%lld", &n, &m, &mod); ++n, ++m;//因为要考虑常数项，所以+1
for(int i = 0;i < n;i ++) scanf("%lld", &x), A[i] = Int(x % mod);
for(int i = 0;i < m;i ++) scanf("%lld", &x), B[i] = Int(x % mod);
Poly::init(n + m);
Poly::NTT(A), Poly::NTT(B);//系数转化为点值
for(int i = 0;i < Poly::lim;i ++) C[i] = A[i] * B[i];//点值逐项相乘
Poly::NTT(C,0);//反向转化（即op=0），点值转回系数
for(int i = 0;i < n+m-1;i ++) printf("%lld ",C[i].get());
printf("\n");return 0;
}
|
