結果

問題 No.1307 Rotate and Accumulate
ユーザー 0w1
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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];
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0