Submission #157598

#	Time	Username	Problem	Language	Result	Execution time	Memory
157598		exqt	씽크스몰 (kriii3_TT)	C++17	20 / 30	7208 ms	56688 KiB

tt

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;

int A, B, P, R;
const int SZ = 21, N = 1 << SZ;

int p[N];
int q[N];

int a[N];
int b[N];
int c[N];
int d[N];

int Pow(int x, int y) {
  int r = 1;
  while (y) {
    if (y & 1) r = (long long)r * x % P;
    x = (long long)x * x % P;
    y >>= 1;
  }
  return r;
}
// code by cubelover
void FFT(int *a, bool f) {
  int i, j, k, x, y, z;
  j = 0;
  for (i = 1; i < N; i++) {
    for (k = N >> 1; j >= k; k >>= 1) j -= k;
    j += k;
    if (i < j) {
      k = a[i];
      a[i] = a[j];
      a[j] = k;
    }
  }
  for (i = 1; i < N; i <<= 1) {
    x = Pow(f ? Pow(R, P - 2) : R, P / i >> 1);
    for (j = 0; j < N; j += i << 1) {
      y = 1;
      for (k = 0; k < i; k++) {
        z = (long long)a[i | j | k] * y % P;
        a[i | j | k] = a[j | k] - z;
        if (a[i | j | k] < 0) a[i | j | k] += P;
        a[j | k] += z;
        if (a[j | k] >= P) a[j | k] -= P;
        y = (long long)y * x % P;
      }
    }
  }
  if (f) {
    j = Pow(N, P - 2);
    for (i = 0; i < N; i++) a[i] = (long long)a[i] * j % P;
  }
}


int main(int argc, char **argv) {
#ifdef LOCAL
  freopen("in.txt", "r", stdin);
#endif
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int n, m; cin >> n >> m;
  for(int i=0; i<=n; i++) cin >> p[i];
  for(int i=0; i<=m; i++) cin >> q[i];

  A = 119, B = 23, P = A << B | 1, R = 3;
  memcpy(a, p, sizeof(p));
  memcpy(b, q, sizeof(q));
  FFT(a, 0);
  FFT(b, 0);
  for(int i=0; i<N; i++) c[i] = (1LL*a[i]*b[i])%P;
  FFT(c, 1);

  A = 7, B = 26, P = A << B | 1, R = 3;
  memcpy(a, p, sizeof(p));
  memcpy(b, q, sizeof(q));
  FFT(a, 0);
  FFT(b, 0);
  for(int i=0; i<N; i++) d[i] = (1LL*a[i]*b[i])%P;
  FFT(d, 1);

  int m1 = 119 << 23 | 1;
  int m2 = 7 << 26 | 1;
  P = m1;
  int inv = Pow(m2, m1-2);

  ll res = 0;
  for(int i=0; i<=n+m; i++) {
    ll q2 = (c[i] - d[i] + m1) % m1;
    q2 = (q2 * inv) % m1;
    ll x = q2*m2+d[i];
    res ^= x;
  }
  cout << res << endl;

  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10