結果
問題 | No.1839 Concatenation Matrix |
ユーザー |
![]() |
提出日時 | 2021-12-12 23:37:30 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 115 ms / 3,500 ms |
コード長 | 900 bytes |
コンパイル時間 | 2,541 ms |
コンパイル使用メモリ | 142,496 KB |
実行使用メモリ | 7,428 KB |
最終ジャッジ日時 | 2024-09-15 14:46:46 |
合計ジャッジ時間 | 4,488 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 16 |
ソースコード
#include <iostream> #include <vector> using namespace std; #include <atcoder/modint> using mint = atcoder::modint998244353; #include <atcoder/convolution> int main() { cin.tie(nullptr), ios::sync_with_stdio(false); int N; cin >> N; vector<mint> A(N); for (auto &a : A) { int x; cin >> x; a = x; } vector<mint> ps{10}; while (int(ps.size()) < N) { auto b = ps.back(); ps.push_back(b * b); } auto rec = [&](auto &&self, int l, int r) -> vector<mint> { if (l + 1 == r) return {1, ps[l]}; int c = (l + r) / 2; return atcoder::convolution(self(self, l, c), self(self, c, r)); }; auto vs = atcoder::convolution(A, rec(rec, 0, N - 1)); vector<mint> ret(N); for (int i = 0; i < int(vs.size()); ++i) ret[(i + 1) % ret.size()] += vs[i]; for (auto x : ret) cout << x.val() << '\n'; }