結果
問題 |
No.1533 Don't be Negative!
|
ユーザー |
👑 ![]() |
提出日時 | 2021-05-28 00:52:05 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,076 bytes |
コンパイル時間 | 12,903 ms |
コンパイル使用メモリ | 287,636 KB |
最終ジャッジ日時 | 2025-01-21 18:51:43 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 13 RE * 40 |
ソースコード
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; #include <atcoder/modint> using Modint = atcoder::modint998244353; int main(){ int N, M, K; cin >> N >> M >> K; if(N > 1e4) abort(); const Modint s = M * 2 - 1 + (K == 0); vector<Modint> a = {1}, b = {0, 1}, a2; Modint ans = 0; for(int i = 0; i < N; i++){ a2.assign(a.size() + M * 2, 0); for(int i = 0; i < b.size() - 1; i++) a2[i] += b[i + 1]; for(int i = b.size() - 1; i < a2.size(); i++) a2[i] += b.back(); for(int i = 1; i < b.size() - 1; i++) a2.end()[-i] -= b.rbegin()[i]; for(int i = 0; i < a.size(); i++) a2[i + M + K] -= a[i]; if(K) for(int i = 0; i < a.size(); i++) a2[i + M - K] -= a[i]; swap(a, a2); b.resize(a.size() + 1); for(int i = 0; i < a.size(); i++) b[i + 1] = b[i] + a[i]; ans *= s; ans += b[M * (i + 1)] * (N - i); } cout << ans.val() << endl; }