結果
問題 | No.1307 Rotate and Accumulate |
ユーザー | pes_magic |
提出日時 | 2020-12-17 19:59:16 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 310 ms / 5,000 ms |
コード長 | 1,911 bytes |
コンパイル時間 | 884 ms |
コンパイル使用メモリ | 80,660 KB |
実行使用メモリ | 13,720 KB |
最終ジャッジ日時 | 2023-10-21 07:06:19 |
合計ジャッジ時間 | 5,174 ms |
ジャッジサーバーID (参考情報) |
judge9 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
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 | 3 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 | AC | 123 ms
9,104 KB |
testcase_09 | AC | 132 ms
9,104 KB |
testcase_10 | AC | 146 ms
8,576 KB |
testcase_11 | AC | 113 ms
8,840 KB |
testcase_12 | AC | 145 ms
8,576 KB |
testcase_13 | AC | 32 ms
4,348 KB |
testcase_14 | AC | 66 ms
5,936 KB |
testcase_15 | AC | 310 ms
13,720 KB |
testcase_16 | AC | 304 ms
13,720 KB |
testcase_17 | AC | 293 ms
13,720 KB |
testcase_18 | AC | 267 ms
13,720 KB |
testcase_19 | AC | 290 ms
13,720 KB |
testcase_20 | AC | 294 ms
13,720 KB |
testcase_21 | AC | 2 ms
4,348 KB |
ソースコード
#include <iostream> #include <vector> #include <algorithm> using namespace std; const int MOD = 998244353; long long modPow(long long a, long long p){ if(p == 0) return 1; auto res = modPow(a, p/2); res = (res*res)%MOD; if(p%2) res = (res*a)%MOD; return res; } long long calcInv(long long a){ return modPow(a, MOD-2); } void ntt(vector<long long>& v, int inv){ const int n = v.size(); auto w = modPow(3, (MOD-1)/n); if(inv == -1) w = calcInv(w); int rev = 0; for(int i=1;i<n-1;i++){ for(int j=n/2;j>(rev^=j);j/=2); if(i < rev) swap(v[i], v[rev]); } for(int m=1;m<n;m*=2){ auto cur = 1; auto rot = modPow(w, n/(2*m)); for(int i=0;i<m;i++){ for(int j=i;j<n;j+=2*m){ auto p = v[j]; auto q = v[j+m] * cur % MOD; v[j] = (p + q) % MOD; v[j+m] = (p + MOD - q) % MOD; } cur = (cur * rot) % MOD; } } } vector<long long> convolution(const vector<long long>& a, const vector<long long>& b){ int _n = a.size() + b.size(); int n = 1; while(n < _n) n *= 2; vector<long long> na(n, 0), nb(n, 0); for(int i=0;i<a.size();i++) na[i] = a[i]; for(int i=0;i<b.size();i++) nb[i] = b[i]; ntt(na, 1); ntt(nb, 1); for(int i=0;i<n;i++) na[i] = na[i] * nb[i] % MOD; ntt(na, -1); auto inv = calcInv(n); for(int i=0;i<n;i++) na[i] = na[i] * inv % MOD; return na; } int main(){ int N, Q; while(cin >> N >> Q){ vector<long long> A(N), B(2*N, 0); for(auto& t : A) cin >> t; for(int i=0;i<Q;i++){ int r; cin >> r; r = (N-r)%N; B[r]++; B[r+N]++; } auto res = convolution(A, B); cout << res[N]; for(int i=1;i<N;i++) cout << " " << res[N+i]; cout << endl; } }