結果
問題 | No.1307 Rotate and Accumulate |
ユーザー |
![]() |
提出日時 | 2020-12-04 00:40:06 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 290 ms / 5,000 ms |
コード長 | 2,810 bytes |
コンパイル時間 | 1,413 ms |
コンパイル使用メモリ | 116,896 KB |
最終ジャッジ日時 | 2025-01-16 15:03:55 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include <iostream>#include <algorithm>#include <iomanip>#include <vector>#include <queue>#include <set>#include <map>#include <cassert>#include <complex>#define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl;#define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl;template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }using namespace std;typedef long long ll;vector<complex<double>> fft(vector<complex<double>> a, bool inverse = false) {int n = a.size();int h = 0;for (int i = 0; 1 << i < n; i++) h++;for (int i = 0; i < n; i++) {int j = 0;for (int k = 0; k < h; k++) j |= (i >> k & 1) << (h - 1 - k);if (i < j) swap(a[i], a[j]);}for (int b = 1; b < n; b *= 2) {for (int j = 0; j < b; j++) {complex<double> w =polar(1.0, (2 * M_PI) / (2 * b) * j * (inverse ? 1 : -1));for (int k = 0; k < n; k += b * 2) {complex<double> s = a[j + k];complex<double> t = a[j + k + b] * w;a[j + k] = s + t;a[j + k + b] = s - t;}}}if (inverse)for (int i = 0; i < n; i++) a[i] /= n;return a;}vector<complex<double>> fft(vector<double> a, bool inverse = false) {vector<complex<double>> a_complex(a.size());for (int i = 0; i < a.size(); i++) a_complex[i] = complex<double>(a[i], 0);return fft(a_complex, inverse);}vector<double> convolve(vector<double> a, vector<double> b) {int s = a.size() + b.size() - 1;int t = 1;while (t < s) t *= 2;a.resize(t);b.resize(t);vector<complex<double>> A = fft(a);vector<complex<double>> B = fft(b);for (int i = 0; i < t; i++) {A[i] *= B[i];}A = fft(A, true);a.resize(s);for (int i = 0; i < s; i++) a[i] = A[i].real();return a;}int n, q;const double eps = 0.01;int main(){ios::sync_with_stdio(false);cin.tie(0);cout << setprecision(10) << fixed;cin >> n >> q;vector<ll> a(n);vector<int> r(q);vector<int> cnt(n);for(int i = 0; i < n; i++) cin >> a[i];for(int i = 0; i < q; i++) {cin >> r[i];cnt[(n-r[i])%n]++;}vector<double> u(n), v(n);for(int i = 0; i < n; i++) u[i] = a[i];for(int i = 0; i < n; i++) v[i] = cnt[i];auto t = convolve(u, v);vector<int> ans(n);for(int i = 0; i < t.size(); i++){ans[i%n] += (int)(t[i]+eps);}for(int i = 0; i < n; i++) cout << ans[i] << ' ';cout << endl;}