結果
問題 | No.1839 Concatenation Matrix |
ユーザー | 👑 hitonanode |
提出日時 | 2021-12-19 17:52:47 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 118 ms / 3,500 ms |
コード長 | 1,118 bytes |
コンパイル時間 | 8,133 ms |
コンパイル使用メモリ | 240,244 KB |
実行使用メモリ | 7,504 KB |
最終ジャッジ日時 | 2023-10-13 18:59:31 |
合計ジャッジ時間 | 10,375 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,352 KB |
testcase_01 | AC | 2 ms
4,348 KB |
testcase_02 | AC | 2 ms
4,356 KB |
testcase_03 | AC | 2 ms
4,352 KB |
testcase_04 | AC | 2 ms
4,352 KB |
testcase_05 | AC | 2 ms
4,348 KB |
testcase_06 | AC | 2 ms
4,348 KB |
testcase_07 | AC | 2 ms
4,352 KB |
testcase_08 | AC | 3 ms
4,348 KB |
testcase_09 | AC | 4 ms
4,352 KB |
testcase_10 | AC | 29 ms
4,420 KB |
testcase_11 | AC | 117 ms
7,488 KB |
testcase_12 | AC | 118 ms
7,340 KB |
testcase_13 | AC | 117 ms
7,500 KB |
testcase_14 | AC | 116 ms
7,504 KB |
testcase_15 | AC | 117 ms
7,464 KB |
testcase_16 | AC | 81 ms
5,732 KB |
testcase_17 | AC | 85 ms
5,656 KB |
testcase_18 | AC | 101 ms
6,848 KB |
ソースコード
// Validator #include "testlib.h" #include <iostream> #include <vector> using namespace std; #include <atcoder/modint> using mint = atcoder::modint998244353; #include <atcoder/convolution> int main(int argc, char **argv) { registerValidation(argc, argv); int N = inf.readInt(2, 100000); inf.readEoln(); vector<mint> A(N); for (int i = 0; i < N; ++i) { int x = inf.readInt(1, 9); if (i + 1 == N) { inf.readEoln(); } else { inf.readSpace(); } A[i] = x; } inf.readEof(); 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'; }