Submission #2487505

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

template< unsigned mod, unsigned primitiveroot >
struct NumberTheoreticTransform {

  vector< vector< unsigned > > rts, rrts;

  void ensure_base(unsigned N) {
    if(rts.size() >= N) return;
    rts.resize(N), rrts.resize(N);
    for(unsigned i = 1; i < N; i <<= 1) {
      if(rts[i].size()) continue;
      unsigned w = mod_pow(primitiveroot, (mod - 1) / (i * 2));
      unsigned rw = inverse(w);
      rts[i].resize(i), rrts[i].resize(i);
      rts[i][0] = 1, rrts[i][0] = 1;
      for(int k = 1; k < i; k++) {
        rts[i][k] = mul(rts[i][k - 1], w);
        rrts[i][k] = mul(rrts[i][k - 1], rw);
      }
    }
  }

  inline unsigned mod_pow(unsigned x, unsigned n) {
    unsigned ret = 1;
    while(n > 0) {
      if(n & 1) ret = mul(ret, x);
      x = mul(x, x);
      n >>= 1;
    }
    return ret;
  }

  inline unsigned inverse(unsigned x) {
    return mod_pow(x, mod - 2);
  }

  inline unsigned add(unsigned x, unsigned y) {
    x += y;
    if(x >= mod) x -= mod;
    return x;
  }

  inline unsigned mul(unsigned a, unsigned b) {
    return unsigned(1LL * a * b % mod);
  }

  void DiscreteFourierTransform(vector< unsigned > &F, bool rev) {
    const unsigned N = (int) F.size();
    ensure_base(N);
    for(unsigned i = 0, j = 1; j + 1 < N; j++) {
      for(unsigned k = N >> 1; k > (i ^= k); k >>= 1);
      if(i > j) swap(F[i], F[j]);
    }
    for(int i = 1; i < N; i <<= 1) {
      for(int j = 0; j < N; j += i * 2) {
        for(int k = 0; k < i; k++) {
          unsigned s = F[j + k], t = mul(F[j + k + i], rev ? rrts[i][k] : rts[i][k]);
          F[j + k] = add(s, t), F[j + k + i] = add(s, mod - t);
        }
      }
    }
    if(rev) {
      unsigned temp = inverse(N);
      for(int i = 0; i < N; i++) F[i] = mul(F[i], temp);
    }
  }

  vector< unsigned > Multiply(const vector< int > &A, const vector< int > &B) {
    int sz = 1;
    while(sz < A.size() + B.size() - 1) sz <<= 1;
    vector< unsigned > F(sz), G(sz);
    for(int i = 0; i < A.size(); i++) F[i] = A[i];
    for(int i = 0; i < B.size(); i++) G[i] = B[i];
    DiscreteFourierTransform(F, false);
    DiscreteFourierTransform(G, false);
    for(int i = 0; i < sz; i++) F[i] = mul(F[i], G[i]);
    DiscreteFourierTransform(F, true);
    F.resize(A.size() + B.size() - 1);
    return (F);
  }
};

const int mod = 1012924417;
const int primitiveRoot = 5;

int main() {
  int N;
  scanf("%d", &N);
  vector< int > A(N + 1), B(N + 1);
  for(int i = 0; i < N; i++) scanf("%d %d", &A[i + 1], &B[i + 1]);
  NumberTheoreticTransform< mod, primitiveRoot > ntt;
  auto C = ntt.Multiply(A, B);
  for(int i = 1; i <= 2 * N; i++) printf("%d\n", C[i]);
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:91:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &N);
                  ^
./Main.cpp:93:66: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   for(int i = 0; i < N; i++) scanf("%d %d", &A[i + 1], &B[i + 1]);
                                                                  ^

Judge Result