結果
問題 | No.1307 Rotate and Accumulate |
ユーザー |
![]() |
提出日時 | 2020-12-04 21:58:05 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 293 ms / 5,000 ms |
コード長 | 1,609 bytes |
コンパイル時間 | 1,175 ms |
コンパイル使用メモリ | 98,412 KB |
最終ジャッジ日時 | 2025-01-16 16:08:20 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include <vector>#include <iostream>#include <complex>using namespace std;using C = complex<double>;const double PI = acos(-1);void fft(vector<C> &a, bool inv) {int n = a.size();if (n == 1) return;vector<C> a0(n / 2), a1(n / 2);for (int i = 0; 2 * i < n; i++) {a0[i] = a[2*i];a1[i] = a[2*i+1];}fft(a0, inv);fft(a1, inv);const double ang = 2 * PI / n * (inv ? -1 : 1);const C wn(cos(ang), sin(ang));C w(1);for (int i = 0; 2 * i < n; i++) {a[i] = a0[i] + w * a1[i];a[i + n/2] = a0[i] - w * a1[i];if (inv) {a[i] /= 2;a[i + n/2] /= 2;}w *= wn;}}vector<long long> multiply(vector<int> const& a, vector<int> const& b) {vector<C> fa(a.begin(), a.end()), fb(b.begin(), b.end());int n = 1;while (n < a.size() + b.size())n <<= 1;fa.resize(n);fb.resize(n);fft(fa, false);fft(fb, false);for (int i = 0; i < n; i++)fa[i] *= fb[i];fft(fa, true);vector<long long> result(n);for (int i = 0; i < n; i++)result[i] = round(fa[i].real());return result;}int main() {int n, q; cin >> n >> q;vector<int> a(n, 0), b(n+1, 0);for (int i = 0; i < n; i++) {cin >> a[i];}while (q--) {int r; cin >> r;b[n-r]++;}vector<long long> v = multiply(a, b);for (int i = 0; i < n; i++) {long long ans = 0;for (int j = i; j < v.size(); j += n) ans += v[j];cout << ans << ' ';}cout << endl;}