結果
問題 | No.1307 Rotate and Accumulate |
ユーザー |
|
提出日時 | 2020-12-24 03:03:30 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 91 ms / 5,000 ms |
コード長 | 2,059 bytes |
コンパイル時間 | 2,178 ms |
コンパイル使用メモリ | 203,196 KB |
最終ジャッジ日時 | 2025-01-17 06:37:31 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#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];}}