![\"g^{P-1}=1(mod\\\\](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/08\/20260802144049-6a6f56f1d8cad.png\")
，\u539f\u6839\u4e3a\u00a0![\"g=\\\\frac{P-1}{n}\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/08\/20260802144049-6a6f56f1e77f0.png\")
\u3002<\/p>\n\u6311\u4e86\u4e2a\u6700\u96be\u5b66\u7684\u4e1c\u897f\u505a\u5417\u3002\u5f88\u6709\u8010\u529b\u4e86\u3002<\/p>\n
\u4e0b\u6b21\u505a\u70b9 noip \u8003\u7eb2\u5185\u7684\u3002<\/p>\n
\u6ca1\u5b66\u8fc7 ntt \u6307\u8def：\u3010FFT & NTT | \u90a3\u5fd8\u7b97 7\u3011\u5feb\u901f\u5085\u91cc\u53f6\u53d8\u6362 & \u5feb\u901f\u6570\u8bba\u53d8\u6362 (\u6d1b\u8c37 P3803 \u9898\u89e3)_\u5085\u91cc\u53f6 \u6d1b\u8c37-CSDN\u535a\u5ba2<\/p>\n<\/p>\n<\/p>\n
ntt \u7684\u5e95\u5c42\u903b\u8f91\u662f\u539f\u6839，\u5373\u00a0，\u539f\u6839\u4e3a\u00a0\u3002<\/p>\n
\u8981\u6c42\u662f\u4e00\u5b9a\u6574\u9664，\u6240\u4ee5\u6a21\u6570\u90fd\u662f\u9009\u00a0![\"2^{x}+1\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/08\/20260802144049-6a6f56f1ec1b3.png\")
\u00a0\u7684\u5f62\u5f0f，\u8fd9\u6837\u00a0![\"n(limit)\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/08\/20260802144049-6a6f56f1f0898.png\")
\u00a0 \u624d\u597d\u9009\u6210 2 \u7684\u5e42\u6b21\u65b9\u4fbf\u5206\u6cbb\u3002<\/p>\n
\u90a3\u4e48\u6b63\u5e38\u4eba\u90fd\u77e5\u9053，\u6a21\u6570\u00a0![\"P-1\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/08\/20260802144050-6a6f56f200d65.png\")
\u00a0\u7684\u00a0![\"2\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/08\/20260802144050-6a6f56f205489.png\")
\u00a0\u56e0\u5b50\u8d8a\u591a\u8d8a\u597d\u3002<\/p>\n
\u800c\u8fd9\u9053\u9898，![\"1000000006](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/08\/20260802144050-6a6f56f209d4d.png\")
，\u4e5f\u5c31\u662f ntt \u7684\u6709\u6548\u4f4d，\u5c45\u7136\u662f ![\"1\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/08\/20260802144050-6a6f56f21074f.png\")
\u00a0\u8036！<\/p>\n
\u76f4\u63a5\u7528\u00a0\u00a0\u80af\u5b9a\u4e0d\u884c，\u90a3\u6211\u4eec\u80fd\u4e0d\u80fd\u7528\u5bf9 ntt \u53cb\u597d\u7684\u6a21\u6570\u7559\u4e0b\u7684\u4f59\u6570，\u6784\u6210\u8fd9\u9053\u9898\u7684\u7b54\u6848\u5462？<\/p>\n<\/p>\n<\/p>\n
\u5047\u8bbe\u6211\u4eec\u73b0\u5728\u6709\u5982\u4e0b，\u800c\u4e14\u6a21\u6570\u4e24\u4e24\u4e92\u8d28：<\/p>\n
x \u2261 r1 (mod P1)
\nx \u2261 r2 (mod P2)
\nx \u2261 r3 (mod P3)
\n…
\nx \u2261 rk (mod Pk) <\/p>\n
\u7528\u8fd9\u4e9b\u6761\u4ef6，\u6784\u9020\u6210\u00a0![\"mod\\\\](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/08\/20260802144050-6a6f56f2195a2.png\")
\u00a0\u7684\u7b54\u6848\u3002<\/p>\n
\u4f17\u4eba\u9ad8\u558a：CRT！\u4e2d\u56fd\u5269\u4f59\u5b9a\u7406！<\/p>\n
\u90a3\u4e48\u9009\u51e0\u4e2a\u6a21\u6570\u597d\u5462？<\/p>\n
\u4ee5\u4e0b\u662f\u00a0ntt \u53cb\u597d\u6a21\u6570：<\/p>\n
P1 = 998244353
\nP2 = 1004535809
\nP3 = 469762049
\n\/\/ gcd(P1, P2) = gcd(P1, P3) = gcd(P2, P3) = 1 \u2713 <\/p>\n
crt \u80fd\u6062\u590d\u7684\u552f\u4e00\u503c\u5728\u00a0[0, M)\u00a0\u8303\u56f4\u5185，\u5176\u4e2d\u00a0M = m1\u00d7m2\u00d7…\u00d7mk\u3002<\/p>\n
\u8fd9\u9053\u9898\u8ba1\u7b97\u53ef\u80fd\u5f97\u5230\u7684\u6700\u5927\u503c\u4e3a\u00a0![\"1000000007*1000000007=1.000000014*10^{18}\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/08\/20260802144050-6a6f56f21dd3c.png\")
<\/p>\n
\u628a\u4e0a\u9762\u54ea\u4ee8\u4e58\u8d77\u6765\u5c31\u5dee\u4e0d\u591a\u4e86\u3002<\/p>\n<\/p>\n<\/p>\n
\u5047\u8bbe\u6211\u4eec\u5df2\u7ecf\u5f97\u5230\u4f59\u6570 r1,r2，\u6a21\u6570\u4e3a P1,P2，\u6709\u00a0![\"x](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/08\/20260802144050-6a6f56f225d0a.png\")
\u3002<\/p>\n
x = r1 + P1 \u00d7 k1
\n\u4ee3\u5165\u7b2c\u4e8c\u4e2a：r1 + P1 \u00d7 k1 \u2261 r2 (mod P2)
\nP1 \u00d7 k1 \u2261 r2 – r1 (mod P2)
\nk1 \u2261 (r2 – r1) \u00d7 P1^(-1) (mod P2) <\/p>\n
\u8fd9\u6837\u5c31\u80fd\u6c42\u51fa\u6ee1\u8db3\u7b2c\u4e00\u3001\u4e8c\u4e2a\u6a21\u6570\u7684 x\u3002<\/p>\n
\u4ee4 x12 = r1 + P1 \u00d7 k1 (\u8fd9\u662f\u6a21P1\u00d7P2\u4e0b\u7684\u89e3)
\nx12 \u2261 r3 (mod P3)
\n\u8bbe x12 + P1\u00d7P2 \u00d7 k2 \u2261 r3 (mod P3)
\nP1\u00d7P2 \u00d7 k2 \u2261 r3 – x12 (mod P3)
\nk2 \u2261 (r3 – x12) \u00d7 (P1\u00d7P2)^(-1) (mod P3) <\/p>\n
\u8fd9\u6837\u5c31\u80fd\u6c42\u51fa\u6ee1\u8db3\u6240\u6709\u6a21\u6570\u7684 x\u3002<\/p>\n<\/p>\n<\/p>\n
#include<bits\/stdc++.h>
\nusing namespace std;<\/p>\n
typedef long long LL;
\ntypedef __int128 i128;
\nconst int N = 3e6 + 10;
\nconst LL MOD = 1000000007;<\/p>\n
const LL P1 = 998244353;
\nconst LL P2 = 1004535809;
\nconst LL P3 = 469762049;<\/p>\n
LL a1[N], b1[N], a2[N], b2[N], a3[N], b3[N];
\nLL ans1[N], ans2[N], ans3[N];
\nLL temp_a[N], temp_b[N];
\nint limit, l, r[N];
\nint n, m;<\/p>\n
LL q_pow(LL a, LL b, LL P) {
\n LL c = 1;
\n while (b) {
\n if (b & 1) c = (i128)c * a % P;
\n a = (i128)a * a % P;
\n b >>= 1;
\n }
\n return c;
\n}<\/p>\n
\/\/ NTT \u5b9e\u73b0
\n\/\/ type = 1: \u6b63\u53d8\u6362, type = -1: \u9006\u53d8\u6362
\nvoid ntt(LL *a, int type, LL P) {
\n for (int i = 0; i < limit; i++) {
\n if (i < r[i]) swap(a[i], a[r[i]]);
\n }<\/p>\n
for (int mid = 1; mid < limit; mid <<= 1) {
\n \/\/ \u8ba1\u7b97\u539f\u6839 g \u7684 (P-1)\/(2*mid) \u6b21\u65b9
\n LL Wn = q_pow(3, (P – 1) \/ (mid << 1), P);
\n if (type == -1) {
\n Wn = q_pow(Wn, P – 2, P); \/\/ \u9006\u53d8\u6362\u53d6\u9006
\n }<\/p>\n
for (int R = (mid << 1), j = 0; j < limit; j += R) {
\n LL w = 1;
\n for (int k = 0; k < mid; k++, w = (i128)w * Wn % P) {
\n LL x = a[j + k];
\n LL y = (i128)a[j + mid + k] * w % P;
\n a[j + k] = (x + y) % P;
\n a[j + mid + k] = (x – y + P) % P;
\n }
\n }
\n }<\/p>\n
\/\/ \u5982\u679c\u662f\u9006\u53d8\u6362，\u4e58\u4ee5 inv_limit
\n if (type == -1) {
\n LL inv_limit = q_pow(limit, P – 2, P);
\n for (int i = 0; i < limit; i++) {
\n a[i] = (i128)a[i] * inv_limit % P;
\n }
\n }
\n}<\/p>\n
void cvlt(LL *a, LL *b, LL *result, LL P) {
\n \/\/ \u590d\u5236\u6570\u636e\u5e76\u6e05\u96f6\u5269\u4f59\u90e8\u5206
\n for (int i = 0; i < limit; i++) {
\n temp_a[i] = (i < n) ? a[i] % P : 0;
\n temp_b[i] = (i < m) ? b[i] % P : 0;
\n }<\/p>\n
\/\/ \u6b63\u53d8\u6362
\n ntt(temp_a, 1, P);
\n ntt(temp_b, 1, P);<\/p>\n
\/\/ \u70b9\u4e58
\n for (int i = 0; i < limit; i++) {
\n temp_a[i] = (i128)temp_a[i] * temp_b[i] % P;
\n }<\/p>\n
\/\/ \u9006\u53d8\u6362
\n ntt(temp_a, -1, P);<\/p>\n
\/\/ \u590d\u5236\u7ed3\u679c
\n for (int i = 0; i < limit; i++) {
\n result[i] = temp_a[i];
\n }
\n}<\/p>\n
LL inv(LL a, LL mod) {
\n return q_pow(a, mod – 2, mod);
\n}<\/p>\n
LL crt(LL r1, LL r2, LL r3) {
\n LL k1 = (r2 – r1) % P2;
\n if (k1 < 0) k1 += P2;
\n k1 = (i128)k1 * inv(P1 % P2, P2) % P2;<\/p>\n
i128 x12 = (i128)r1 + (i128)P1 * k1;
\n i128 P12 = (i128)P1 * P2;<\/p>\n
LL r3_mod = (LL)(x12 % P3);
\n LL k2 = (r3 – r3_mod) % P3;
\n if (k2 < 0) k2 += P3;
\n k2 = (i128)k2 * inv((LL)(P12 % P3), P3) % P3;<\/p>\n
i128 x = x12 + P12 * k2;
\n x %= MOD;<\/p>\n
return (LL)x;
\n}<\/p>\n
int main() {
\n ios::sync_with_stdio(false);
\n cin.tie(0);<\/p>\n
cin >> n >> m;<\/p>\n
for (int i = 0; i < n; i++) {
\n cin >> a1[i];
\n a2[i] = a3[i] = a1[i];
\n }
\n for (int i = 0; i < m; i++) {
\n cin >> b1[i];
\n b2[i] = b3[i] = b1[i];
\n }<\/p>\n
limit = 1;
\n l = 0;
\n while (limit < n + m – 1) {
\n limit <<= 1;
\n l ++;
\n }<\/p>\n
\/\/ \u8ba1\u7b97\u4f4d\u9006\u5e8f
\n for (int i = 0; i < limit; i++) {
\n r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l – 1));
\n }<\/p>\n
\/\/ \u5206\u522b\u5728\u4e09\u4e2a\u6a21\u6570\u4e0b\u8ba1\u7b97\u5377\u79ef
\n cvlt(a1, b1, ans1, P1);
\n cvlt(a2, b2, ans2, P2);
\n cvlt(a3, b3, ans3, P3);<\/p>\n
\/\/ \u8f93\u51fa\u7ed3\u679c
\n for (int i = 0; i < n + m – 1; i++) {
\n LL res = crt(ans1[i], ans2[i], ans3[i]);
\n cout << res << " ";
\n }
\n cout << "\\\\n";<\/p>\n
return 0;
\n} <\/p>\n","protected":false},"excerpt":{"rendered":"
\u6311\u4e86\u4e2a\u6700\u96be\u5b66\u7684\u4e1c\u897f\u505a\u5417\u3002\u5f88\u6709\u8010\u529b\u4e86\u3002
\n\u4e0b\u6b21\u505a\u70b9 noip \u8003\u7eb2\u5185\u7684\u3002 \u6ca1\u5b66\u8fc7 ntt \u6307\u8def：\u3010FFT & NTT | \u90a3\u5fd8\u7b97 7\u3011\u5feb\u901f\u5085\u91cc\u53f6\u53d8\u6362 & \u5feb\u901f\u6570\u8bba\u53d8\u6362 (\u6d1b\u8c37 P3803 \u9898\u89e3)_\u5085\u91cc\u53f6 \u6d1b\u8c37-CSDN\u535a\u5ba2 0.\u5bfc\u5165
\nntt \u7684\u5e95\u5c42\u903b\u8f91\u662f\u539f\u6839，\u5373\u00a0，\u539f\u6839\u4e3a\u00a0\u3002
\n\u8981\u6c42\u662f\u4e00\u5b9a\u6574\u9664，\u6240\u4ee5\u6a21\u6570\u90fd\u662f\u9009\u00a0\u00a0\u7684\u5f62\u5f0f，\u8fd9\u6837\u00a0\u00a0 \u624d\u597d\u9009\u6210 2 \u7684\u5e42\u6b21\u65b9\u4fbf\u5206\u6cbb\u3002
\n\u90a3\u4e48\u6b63\u5e38\u4eba\u90fd\u77e5\u9053，\u6a21\u6570\u00a0\u00a0\u7684\u00a0<\/p>\n","protected":false},"author":2,"featured_media":89373,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[10139,10138,55,427],"topic":[],"class_list":["post-89385","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-server","tag-crt","tag-ntt","tag-c","tag-427"],"yoast_head":"\n