結果
問題 | 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';}