ACM_Notebook_new
This documentation is automatically generated by online-judge-tools/verification-helper
Math/tests/ntt_chemthan_any_mod.test.cpp
- View this file on GitHub
- Last update: 2022-08-21 23:32:29+08:00
- Problem: https://judge.yosupo.jp/problem/convolution_mod_1000000007
Depends on
Code
#define PROBLEM "https://judge.yosupo.jp/problem/convolution_mod_1000000007"
#include <bits/stdc++.h>
using namespace std;
#include "../Polynomial/NTT_chemthan.h"
#include "../NumberTheory/CRT_chemthan.h"
const int MOD0 = 167772161;
const int MOD1 = 469762049;
const int MOD2 = 754974721;
NTT<MOD0, 1 << 20> ntt0;
NTT<MOD1, 1 << 20> ntt1;
NTT<MOD2, 1 << 20> ntt2;
#define REP(i, a) for (int i = 0, _##i = (a); i < _##i; ++i)
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, m; cin >> n >> m;
vector<int> a(n); REP(i,n) cin >> a[i];
vector<int> b(m); REP(i,m) cin >> b[i];
auto c0 = ntt0.multiply(a, b);
auto c1 = ntt1.multiply(a, b);
auto c2 = ntt2.multiply(a, b);
const int MOD = 1e9 + 7;
REP(i,n+m-1) {
CRT<__int128_t> crt;
crt.add(MOD0, c0[i]);
crt.add(MOD1, c1[i]);
crt.add(MOD2, c2[i]);
cout << (int) (crt.res % MOD) << ' ';
}
cout << endl;
return 0;
}#line 1 "Math/tests/ntt_chemthan_any_mod.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/convolution_mod_1000000007"
#include <bits/stdc++.h>
using namespace std;
#line 1 "Math/Polynomial/NTT_chemthan.h"
// Copied from chemthan
// 2x slower than atcoder library
// Tested:
// - https://oj.vnoi.info/problem/icpc21_mt_d
// - https://judge.yosupo.jp/problem/convolution_mod
// - https://judge.yosupo.jp/problem/convolution_mod_1000000007
//
// Sample usage: Multiply big-int polynomials using NTT + CRT
// NTT<MOD0, 1 << 21> ntt0;
// NTT<MOD1, 1 << 21> ntt1;
// auto r0 = ntt0.multiply(v1, v2);
// auto r1 = ntt1.multiply(v1, v2);
//
// // Using CRT to combine r0 and r1
// CRT<int> crt;
// crt.add(MOD0, r0[idx]);
// crt.add(MOD1, r1[idx]);
// cout << crt.res << endl;
// mod must be NTT mod
// maxf = max degree of c. Should be 2^k?
template<const int mod, const int maxf>
struct NTT {
NTT() {
int k = 0; while ((1 << k) < maxf) k++;
bitrev[0] = 0;
for (int i = 1; i < maxf; i++) {
bitrev[i] = bitrev[i >> 1] >> 1 | ((i & 1) << (k - 1));
}
int pw = fpow(prt(), (mod - 1) / maxf);
rts[0] = 1;
for (int i = 1; i <= maxf; i++) {
rts[i] = (long long) rts[i - 1] * pw % mod;
}
for (int i = 1; i <= maxf; i <<= 1) {
iv[i] = fpow(i, mod - 2);
}
}
vector<int> multiply(vector<int> a, vector<int> b) {
static int fa[maxf], fb[maxf], fc[maxf];
int na = a.size(), nb = b.size();
for (int i = 0; i < na; i++) fa[i] = a[i];
for (int i = 0; i < nb; i++) fb[i] = b[i];
multiply(fa, fb, na, nb, fc);
int k = na + nb - 1;
vector<int> res(k);
for (int i = 0; i < k; i++) res[i] = fc[i];
return res;
}
private:
int rts[maxf + 1];
int bitrev[maxf];
int iv[maxf + 1];
int fpow(int a, int k) {
if (!k) return 1;
int res = a, tmp = a;
k--;
while (k) {
if (k & 1) {
res = (long long) res * tmp % mod;
}
tmp = (long long) tmp * tmp % mod;
k >>= 1;
}
return res;
}
int prt() {
vector<int> dvs;
for (int i = 2; i * i < mod; i++) {
if ((mod - 1) % i) continue;
dvs.push_back(i);
if (i * i != mod - 1) dvs.push_back((mod - 1) / i);
}
for (int i = 2; i < mod; i++) {
int flag = 1;
for (int j = 0; j < (int) dvs.size(); j++) {
if (fpow(i, dvs[j]) == 1) {
flag = 0;
break;
}
}
if (flag) return i;
}
assert(0);
return -1;
}
void dft(int a[], int n, int sign) {
int d = 0; while ((1 << d) * n != maxf) d++;
for (int i = 0; i < n; i++) {
if (i < (bitrev[i] >> d)) {
swap(a[i], a[bitrev[i] >> d]);
}
}
for (int len = 2; len <= n; len <<= 1) {
int delta = maxf / len * sign;
for (int i = 0; i < n; i += len) {
int *w = sign > 0 ? rts : rts + maxf;
for (int k = 0; k + k < len; k++) {
int &a1 = a[i + k + (len >> 1)], &a2 = a[i + k];
int t = (long long) *w * a1 % mod;
a1 = a2 - t;
a2 = a2 + t;
a1 += a1 < 0 ? mod : 0;
a2 -= a2 >= mod ? mod : 0;
w += delta;
}
}
}
if (sign < 0) {
int in = iv[n];
for (int i = 0; i < n; i++) {
a[i] = (long long) a[i] * in % mod;
}
}
}
void multiply(int a[], int b[], int na, int nb, int c[]) {
static int fa[maxf], fb[maxf];
int n = na + nb - 1; while (n != (n & -n)) n += n & -n;
for (int i = 0; i < n; i++) fa[i] = fb[i] = 0;
for (int i = 0; i < na; i++) fa[i] = a[i];
for (int i = 0; i < nb; i++) fb[i] = b[i];
dft(fa, n, 1), dft(fb, n, 1);
for (int i = 0; i < n; i++) fa[i] = (long long) fa[i] * fb[i] % mod;
dft(fa, n, -1);
for (int i = 0; i < n; i++) c[i] = fa[i];
}
};
/* Examples
const int MOD0 = 1004535809; //2^21 * 479 + 1
const int MOD1 = 1012924417; //2^21 * 483 + 1
const int MOD2 = 998244353; //2^20 * 476 + 1
NTT<MOD0, 1 << 21> ntt0;
NTT<MOD1, 1 << 21> ntt1;
*/
#line 1 "Math/NumberTheory/CRT_chemthan.h"
// CRT {{{
// Tested:
// - https://oj.vnoi.info/problem/icpc21_mt_d
// - (__int128_t) https://judge.yosupo.jp/problem/convolution_mod_1000000007
template<typename T>
struct CRT {
T res;
CRT() {
res = 0, prd = 1;
}
// Add condition: res % p == r
void add(T p, T r) {
res += mul(r - res % p + p, euclid(prd, p).first + p, p) * prd;
prd *= p;
if (res >= prd) res -= prd;
}
private:
T prd;
T mul(T a, T b, T p) {
a %= p, b %= p;
T q = (T) ((long double) a * b / p);
T r = a * b - q * p;
while (r < 0) r += p;
while (r >= p) r -= p;
return r;
}
pair<T, T> euclid(T a, T b) {
if (!b) return make_pair(1, 0);
pair<T, T> r = euclid(b, a % b);
return make_pair(r.second, r.first - a / b * r.second);
}
};
// }}}
#line 8 "Math/tests/ntt_chemthan_any_mod.test.cpp"
const int MOD0 = 167772161;
const int MOD1 = 469762049;
const int MOD2 = 754974721;
NTT<MOD0, 1 << 20> ntt0;
NTT<MOD1, 1 << 20> ntt1;
NTT<MOD2, 1 << 20> ntt2;
#define REP(i, a) for (int i = 0, _##i = (a); i < _##i; ++i)
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, m; cin >> n >> m;
vector<int> a(n); REP(i,n) cin >> a[i];
vector<int> b(m); REP(i,m) cin >> b[i];
auto c0 = ntt0.multiply(a, b);
auto c1 = ntt1.multiply(a, b);
auto c2 = ntt2.multiply(a, b);
const int MOD = 1e9 + 7;
REP(i,n+m-1) {
CRT<__int128_t> crt;
crt.add(MOD0, c0[i]);
crt.add(MOD1, c1[i]);
crt.add(MOD2, c2[i]);
cout << (int) (crt.res % MOD) << ' ';
}
cout << endl;
return 0;
}