Sai0511 @ 2019-12-28 13:42:04
要调自闭了啊啊啊啊啊啊啊啊啊啊啊啊。
#include <bits/stdc++.h>
typedef long long ll;
const int N = 4e5 + 10;
const double pi = acos(-1);
int n, m, i, j, k, mod, lim, L;
ll f[N], g[N], h[N]; int rev[N];
struct comp {
double x, y;
comp() { x = y = 0; }
comp(double _x, double _y) { x = _x, y = _y; }
inline friend comp operator + (comp a, comp b) {
return comp(a.x + b.x, a.y + b.y);
}
inline friend comp operator - (comp a, comp b) {
return comp(a.x - b.x, a.y - b.y);
}
inline friend comp operator * (comp a, comp b) {
// (a + bi)(c + di)
// ac + adi + bci - bd
// (ac - bd, ad + bc)
return comp(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}
} a[N], b[N], c[N], d[N], e[N], I[N], J[N];
inline void init(int items) {
lim = 1, L = 0;
while (lim < items) lim <<= 1, L++;
for (int i = 0; i < lim; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << L - 1);
}
inline void fft(comp a[], int type) {
for (int i = 0; i < lim; i++) if (i < rev[i]) std::swap(a[i], a[rev[i]]);
for (int mid = 1; mid < lim; mid <<= 1) {
comp wn = comp(cos(pi / mid), type * sin(pi / mid));
for (int i = 0, r = mid << 1; i < lim; i += r) {
comp w(1, 0);
for (int j = 0; j < mid; j++, w = w * wn) {
comp x = a[i + j], y = w * a[i + j + mid];
a[i + j] = x + y;
a[i + j + mid] = x - y;
}
}
}
if (type == -1) for (int i = 0; i < lim; i++) a[i].x /= lim, a[i].y /= lim;
}
inline void mtt(ll h[], ll f[], ll g[], int n, int m) {
init(n + m);
for (int i = 0; i < lim; i++) a[i].x = f[i] >> 15, b[i].x = f[i] & 0x7fffffff;
for (int i = 0; i < lim; i++) c[i].x = g[i] >> 15, d[i].x = g[i] & 0x7fffffff;
fft(a, 1), fft(b, 1), fft(c, 1), fft(d, 1);
for (int i = 0; i < lim; i++) {
e[i] = a[i] * c[i];
I[i] = a[i] * d[i] + b[i] * c[i];
J[i] = b[i] * d[i];
}
fft(e, -1), fft(I, -1), fft(J, -1);
for (int i = 0; i < lim; i++) {
ll x = (1ll * (ll)(e[i].x + 0.5) << 30) % mod;
ll y = (1ll * (ll)(I[i].x + 0.5) << 15) % mod;
ll z = 1ll * (ll)(J[i].x + 0.5) % mod;
h[i] = (((x % mod) + y) % mod + z) % mod;
}
}
int main() {
scanf("%d %d %d", &n, &m, &mod);
for (int i = 0; i <= n; i++) scanf("%lld", f + i), f[i] %= mod;
for (int i = 0; i <= m; i++) scanf("%lld", g + i), g[i] %= mod;
mtt(h, f, g, n, m);
for (int i = 0; i <= n + m; i++) printf("%lld ", h[i]); puts("");
return 0;
}
by Serenata_Immortale @ 2019-12-28 13:44:54
@connect pi写成(long double)acos(-1.0)试试
by Sai0511 @ 2019-12-28 13:51:31
@pathogen 把double define成long double还是50分)
by tiger0133 @ 2019-12-28 13:55:49
@installb 诶……这个会出事么
by Sai0511 @ 2019-12-28 14:08:49
@installb 这个很安全吧)因为sin是double类型的啊
by Karry5307 @ 2019-12-28 14:26:08
@connect 尛 connect
by Sai0511 @ 2019-12-28 14:50:58
@Karry5307 多项式大师帮我看看呗/kk
by Karry5307 @ 2019-12-28 15:00:57
@connect 话说 FFT 应该没问题哈?
by Karry5307 @ 2019-12-28 15:15:38
@connect 不应该是
b[i].x = f[i] & 32767;
而不是
b[i].x = f[i] & 0x7fffffff;
by installb @ 2019-12-28 15:44:52
看来我又记错了(? hb
by Sai0511 @ 2019-12-28 17:11:05
@Karry5307 这一样的吧...0x7fff就是32767啊