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 Karry5307 @ 2019-12-28 17:33:08

@connect 不是啊,改成 32767 就对了


by Sai0511 @ 2019-12-28 17:34:57

@Karry5307
我改成32767还是50分(
理论上应该是一样的啊?
不管了


by installb @ 2019-12-28 17:50:43

@connect 您过了吗(
int乘double返回的是int吧
本地测了


by Sai0511 @ 2019-12-28 17:52:16

@installb
orz。
我把单位根预处理出来然后过了


上一页 |