oj.uz

Submission #15141

# Submission time Handle Problem Language Result Execution time Memory
15141 2015-07-11T15:27:07 Z xhae 씽크스몰 (kriii3_TT) C++14
20 / 30
 10000 ms 196592 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);

// 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, const ComplexVector &ws, int step) {
  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, ws, step * 2);
  dft(odd, ws, step * 2);

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

// 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);

  ComplexVector ws(n);
  for (int i = 0; i < n; i++) {
    auto theta = 2 * PI * i / n;
    ws[i] = Complex(cos(theta), sin(theta));
  }

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

  // Inverse FFT
  reverse(ws.begin()+1, ws.end());
  dft(ac, ws, 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 {31627, 31643, 31649, 31657};
  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 1840 KB Output is correct
5 Correct 7 ms 1860 KB Output is correct
6 Correct 5 ms 1860 KB Output is correct
7 Correct 7 ms 1860 KB Output is correct
8 Correct 7 ms 1860 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 4608 KB Output is correct
2 Correct 983 ms 25100 KB Output is correct
3 Correct 1025 ms 25448 KB Output is correct
4 Correct 994 ms 25864 KB Output is correct
5 Correct 998 ms 25976 KB Output is correct
6 Correct 1019 ms 25920 KB Output is correct
7 Correct 1016 ms 25952 KB Output is correct
8 Correct 1011 ms 25952 KB Output is correct

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2149 ms 49416 KB Output is correct
2 Correct 4552 ms 97008 KB Output is correct
3 Correct 4549 ms 98428 KB Output is correct
4 Execution timed out 10000 ms 196592 KB Program timed out
5 Halted 0 ms 0 KB -