oj.uz

Submission #15144

# Submission time Handle Problem Language Result Execution time Memory
15144 2015-07-11T15:46:14 Z xhae 씽크스몰 (kriii3_TT) C++14
30 / 30
 9576 ms 230604 KB 
#include<vector>
#include<complex>
#include<cmath>
#include <ctime>
#include <algorithm>

using namespace std;

typedef complex<double> Complex;
typedef vector<Complex> ComplexVector;
typedef vector<int> Polynomial;
typedef vector<long long> PolynomialLL;

const double PI = 2.0 * acos(0.0);

ComplexVector wcache[22];

// Given a n-th polynomial p, return its values at
// w^0, w^1, .., w^(n-1). n is assumed to be a power of 2.
// Since the size of the input and output are the same, the output is stored at
// p.
void dft(ComplexVector& p, int step, int dir) {
  int n = p.size();
  if(n == 1) return;

  // divide
  ComplexVector even(n / 2), odd(n / 2);
  for(int i = 0; i < n/2; ++i) {
    even[i] = p[i * 2];
    odd[i] = p[i * 2 + 1];
  }

  // conquer
  dft(even, step+1, dir);
  dft(odd, step+1, dir);

  // merge
  int w_power = 0;
  for(int i = 0; i < n/2; ++i) {
    Complex offset = wcache[step][w_power] * odd[i];
    p[i      ] = even[i] + offset;
    p[i + n/2] = even[i] - offset;
    w_power += dir;
    if (w_power < 0) w_power += wcache[step].size();
  }
}

// returns smallest power of 2 s.t. p2 >= n.
int roundUp(int n) {
  int p2 = 1;
  while(p2 < n) p2 *= 2;
  return p2;
}

PolynomialLL operator * (const Polynomial& a, const Polynomial& b) {
  // last *2 is needed because C can have twice the degree from original polys
  int n = roundUp(max(a.size(), b.size())) * 2;

  // Complex representations of a and b
  ComplexVector ac(a.begin(), a.end()), bc(b.begin(), b.end());
  ac.resize(n);
  bc.resize(n);

  if (wcache[0].size() == 0) {
    wcache[0].resize(n);
    for (int i = 0; i < n; i++) {
      auto theta = 2 * PI * i / n;
      wcache[0][i] = Complex(cos(theta), sin(theta));
    }
    for (int step = 0; step < 21; step++) {
      wcache[step+1].resize((wcache[step].size()+1)/2);
      for (int i = 0; i < wcache[step].size(); i += 2) {
        wcache[step+1][i / 2] = wcache[step][i];
      }
    }
  }

  // FFT
  dft(ac, 0, 1);
  dft(bc, 0, 1);
  // Pointwise multiplication
  for(int i = 0; i < n; ++i)
    ac[i] *= bc[i];

  // Inverse FFT
  dft(ac, 0, -1);
  for(int i = 0; i < n; ++i)
    ac[i] /= n;

  // return real
  PolynomialLL ret(ac.size());
  for(int i = 0; i < ac.size(); ++i)
    ret[i] = (long long)(round(real(ac[i])));

  return ret;
}


int main(){
  int n,m;
  vector<int> f, g;
  scanf("%d%d", &n, &m);
  n++; m++;
  for (int i = 0; i < n; i++) {
    int v;
    scanf("%d",&v);
    f.emplace_back(v);
  }
  for (int i = 0; i < m; i++) {
    int v;
    scanf("%d",&v);
    g.emplace_back(v);
  }
  vector<int> mods {4001, 4003, 4007, 4013, 4019};
  vector<int> pinv;
  for (int i = 0; i < mods.size(); i++) {
    int p = 1;
    int q = mods[i];
    for (int j = 0; j < i; j++) p = p * mods[j] % q;
    for (int j = 1; j < q; j++) {
      if (p*j%q == 1) {
        pinv.push_back(j);
        break;
      }
    }
  }
  vector<int> t1, t2;
  t1.resize(f.size());
  t2.resize(g.size());
  vector<long long> ans;

  long long p = 1, q;
  for (int i = 0; i < mods.size(); i++) {
    q = mods[i];
    for (int j = 0; j < f.size(); j++) t1[j] = f[j]%mods[i];
    for (int j = 0; j < g.size(); j++) t2[j] = g[j]%mods[i];
    auto &&tres = t1*t2;
    ans.resize(tres.size());
    for (int j = 0; j < tres.size(); j++) {
      long long ba = (tres[j] - ans[j])%q;
      if (ba < 0) ba += q;
      ans[j] += (ba * pinv[i] % q) * p;
    }
    p *= mods[i];
  }
  long long ansxor = 0;
  for (auto v : ans) {
    ansxor ^= v;
  }
  printf("%lld\n", ansxor);
  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1680 KB Output is correct
2 Correct 0 ms 1680 KB Output is correct
3 Correct 0 ms 1680 KB Output is correct
4 Correct 7 ms 1812 KB Output is correct
5 Correct 7 ms 1824 KB Output is correct
6 Correct 7 ms 1820 KB Output is correct
7 Correct 7 ms 1824 KB Output is correct
8 Correct 7 ms 1824 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 5112 KB Output is correct
2 Correct 1043 ms 29188 KB Output is correct
3 Correct 1044 ms 29460 KB Output is correct
4 Correct 1049 ms 29972 KB Output is correct
5 Correct 1051 ms 30080 KB Output is correct
6 Correct 1059 ms 30024 KB Output is correct
7 Correct 1044 ms 30056 KB Output is correct
8 Correct 1047 ms 30056 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2179 ms 57572 KB Output is correct
2 Correct 4530 ms 113400 KB Output is correct
3 Correct 4506 ms 114820 KB Output is correct
4 Correct 9474 ms 229364 KB Output is correct
5 Correct 9508 ms 228576 KB Output is correct
6 Correct 9576 ms 230056 KB Output is correct
7 Correct 9549 ms 230604 KB Output is correct
8 Correct 9561 ms 230604 KB Output is correct