結果
問題 | No.2279 OR Insertion |
ユーザー |
|
提出日時 | 2023-04-21 22:18:33 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 129 ms / 2,000 ms |
コード長 | 839 bytes |
コンパイル時間 | 3,191 ms |
コンパイル使用メモリ | 245,936 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-06 15:48:23 |
合計ジャッジ時間 | 7,472 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 48 |
ソースコード
#include <bits/stdc++.h> using namespace std; using LL = long long; constexpr LL mod = 998244353; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; string s; cin >> n >> s; LL ans = 0; for (LL k = 1, p = 1; k <= n; k += 1, p = p * 2 % mod) { vector<LL> f(n + 1); vector<LL> g(n + 1); g[0] = 1; for (int i = 1; i <= n; i += 1) { if (i < k or s[i - k] == '0') { g[i] = g[i - 1]; f[i] = f[i - 1]; } else { f[i] = (f[i - 1] + g[i - k]) % mod; g[i] = (g[i - 1] + mod - g[i - k]) % mod; } f[i] = (f[i] + f[i - 1]) % mod; g[i] = (g[i] + g[i - 1]) % mod; } ans = (ans + (f[n] + mod - f[n - 1]) * p) % mod; } cout << ans; }