oj.uz

Submission #157598

# Submission time Handle Problem Language Result Execution time Memory
157598 2019-10-12T14:34:46 Z exqt 씽크스몰 (kriii3_TT) C++17
20 / 30
 7208 ms 56688 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4086 ms 33232 KB Output is correct
2 Correct 4354 ms 33364 KB Output is correct
3 Correct 4831 ms 33204 KB Output is correct
4 Correct 5283 ms 33340 KB Output is correct
5 Correct 5526 ms 33268 KB Output is correct
6 Correct 5517 ms 33392 KB Output is correct
7 Correct 5526 ms 33268 KB Output is correct
8 Correct 5448 ms 33276 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6130 ms 33352 KB Output is correct
2 Correct 6417 ms 33932 KB Output is correct
3 Correct 6454 ms 34080 KB Output is correct
4 Correct 6565 ms 34412 KB Output is correct
5 Correct 6620 ms 34556 KB Output is correct
6 Correct 6595 ms 34572 KB Output is correct
7 Correct 6563 ms 34604 KB Output is correct
8 Correct 5893 ms 35036 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6695 ms 34500 KB Output is correct
2 Correct 6832 ms 39388 KB Output is correct
3 Correct 6878 ms 40356 KB Output is correct
4 Correct 7124 ms 51144 KB Output is correct
5 Correct 7208 ms 49008 KB Output is correct
6 Correct 7147 ms 53024 KB Output is correct
7 Incorrect 6131 ms 56688 KB Output isn't correct
8 Halted 0 ms 0 KB -