mtt WA50求助。。。

P4245 【模板】任意模数多项式乘法

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啊


| 下一页