結果

問題 No.1307 Rotate and Accumulate
ユーザー 0w10w1
提出日時 2020-12-24 03:00:06
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,053 bytes
コンパイル時間 2,581 ms
コンパイル使用メモリ 211,080 KB
実行使用メモリ 22,268 KB
最終ジャッジ日時 2023-10-21 15:32:13
合計ジャッジ時間 6,488 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge9
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 2 ms
4,348 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 2 ms
4,348 KB
testcase_07 AC 2 ms
4,348 KB
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 AC 2 ms
4,348 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 << round(polyC[i]) << " \n"[i + 1 == 2 * N];
  }
}
0