結果
問題 | No.2219 Re:010 |
ユーザー |
![]() |
提出日時 | 2023-02-17 22:11:52 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 9 ms / 2,000 ms |
コード長 | 1,607 bytes |
コンパイル時間 | 429 ms |
コンパイル使用メモリ | 31,744 KB |
実行使用メモリ | 13,032 KB |
最終ジャッジ日時 | 2024-07-19 13:21:35 |
合計ジャッジ時間 | 1,401 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#include <stdio.h> int main () { char s[200001] = ""; int res = 0; long long ans = 0LL; long long mod_num = 998244353LL; int len = 0; int qcnt = 0; long long pow2[200001] = {}; long long dp[200001][6] = {}; res = scanf("%s", s); while (s[len] != '\0') { if (s[len] == '?') { qcnt++; } len++; } pow2[0] = 1LL; for (int i = 0; i < qcnt; i++) { pow2[i+1] = (pow2[i]*2LL)%mod_num; } for (int i = 0; i < len; i++) { if (s[i] == '0') { ans += (dp[i][1]*pow2[qcnt])%mod_num; ans += (dp[i][2]*pow2[qcnt-1])%mod_num; ans += (dp[i][4]*pow2[qcnt-1])%mod_num; ans += (dp[i][5]*pow2[qcnt-2])%mod_num; dp[i+1][0] = (dp[i][0]+1LL)%mod_num; dp[i+1][1] = dp[i][1]; dp[i+1][2] = dp[i][2]; dp[i+1][3] = dp[i][3]; dp[i+1][4] = dp[i][4]; dp[i+1][5] = dp[i][5]; } else if (s[i] == '1') { dp[i+1][0] = dp[i][0]; dp[i+1][1] = (dp[i][1]+dp[i][0])%mod_num; dp[i+1][2] = dp[i][2]; dp[i+1][3] = dp[i][3]; dp[i+1][4] = (dp[i][4]+dp[i][3])%mod_num;; dp[i+1][5] = dp[i][5]; } else { ans += (dp[i][1]*pow2[qcnt-1])%mod_num; ans += (dp[i][2]*pow2[qcnt-2])%mod_num; ans += (dp[i][4]*pow2[qcnt-2])%mod_num; ans += (dp[i][5]*pow2[qcnt-3])%mod_num; dp[i+1][0] = dp[i][0]; dp[i+1][1] = dp[i][1]; dp[i+1][2] = (dp[i][2]+dp[i][0])%mod_num; dp[i+1][3] = (dp[i][3]+1LL)%mod_num; dp[i+1][4] = dp[i][4]; dp[i+1][5] = (dp[i][5]+dp[i][3])%mod_num; } } printf("%lld\n", ans%mod_num); return 0; }