結果

問題 No.1307 Rotate and Accumulate
ユーザー 0w10w1
提出日時 2020-12-24 03:03:30
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 90 ms / 5,000 ms
コード長 2,059 bytes
コンパイル時間 2,320 ms
コンパイル使用メモリ 209,740 KB
実行使用メモリ 22,144 KB
最終ジャッジ日時 2024-09-21 16:46:23
合計ジャッジ時間 4,563 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 69 ms
20,480 KB
testcase_09 AC 71 ms
20,608 KB
testcase_10 AC 50 ms
12,928 KB
testcase_11 AC 40 ms
12,928 KB
testcase_12 AC 49 ms
12,928 KB
testcase_13 AC 13 ms
5,376 KB
testcase_14 AC 26 ms
8,064 KB
testcase_15 AC 90 ms
22,144 KB
testcase_16 AC 90 ms
22,144 KB
testcase_17 AC 90 ms
22,144 KB
testcase_18 AC 85 ms
22,144 KB
testcase_19 AC 90 ms
22,016 KB
testcase_20 AC 90 ms
22,144 KB
testcase_21 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

template<typename CF = complex<double>>
void fft(vector<CF> &p, bool inv = 0) {
  int n = p.size();
  int lg = __builtin_ctz(n);
  assert(n == (1<<lg));

  CF w = exp(-CF(0, 2) * acos(-1.0) / (CF) n);

  for (int j = 1, i = 0; j < n - 1; ++j) {
    for (int k = n >> 1; k > (i^=k); k >>= 1) ;
    if (j < i) swap(p[i], p[j]);
  }

  vector<CF> ws = { inv ? CF(1) / w : w };
  for (int i = 1; i < lg; ++i) ws.push_back(ws[i - 1] * ws[i - 1]);
  reverse(ws.begin(), ws.end());

  for (int i = 0; i < lg; ++i) {
    for (int k = 0; k < n; k += 2<<i) {
      CF base = 1;
      for (int j = k; j < k + (1<<i); ++j, base *= ws[i]) {
        CF t = base * p[j + (1<<i)];
        CF u = p[j];
        p[j] = u + t;
        p[j + (1<<i)] = u - t;
      }
    }
  }

  if (inv) for_each(p.begin(), p.end(), [&](CF &v) { v /= n; });
}

template<typename F = double>
vector<F> polyMul(const vector<F> &a, const vector<F> &b) {
  int n = 1;
  while (n < max(a.size(), b.size())) n *= 2;

  using CF = complex<F>;

  vector<CF> pa(n); {
    for (int i = 0; i < (int) a.size(); ++i) pa[i] = a[i];
    fft(pa);
  }

  vector<CF> pb(n); {
    for (int i = 0; i < (int) b.size(); ++i) pb[i] = b[i];
    fft(pb);
  }

  vector<CF> pc(n); {
    for (int i = 0; i < n; ++i) pc[i] = pa[i] * pb[i];
  }

  vector<F> c(n); {
    fft(pc, 1);
    for (int i = 0; i < n; ++i) c[i] = real(pc[i]);
  }

  return c;
}

int main() {
  ios::sync_with_stdio(false);

  int N, Q; {
    cin >> N >> Q;
  }

  vector<int> A(N); {
    for (int i = 0; i < N; ++i) {
      cin >> A[i];
    }
  }

  vector<int> R(Q); {
    for (int i = 0; i < Q; ++i) {
      cin >> R[i];
    }
  }

  vector<double> polyA(2 * N); {
    for (int i = 0; i < 2 * N; ++i) {
      polyA[i] = A[i % N];
    }
  }

  vector<double> polyB(2 * N); {
    for (int i = 0; i < Q; ++i) {
      polyB[N - R[i]] += 1;
    }
  }

  vector<double> polyC = polyMul(polyA, polyB);

  for (int i = N; i < 2 * N; ++i) {
    cout << (int) round(polyC[i]) << " \n"[i + 1 == 2 * N];
  }
}
0