結果
問題 | No.1710 Minimum OR is X |
ユーザー |
![]() |
提出日時 | 2021-10-03 16:40:36 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 24 ms / 2,000 ms |
コード長 | 1,447 bytes |
コンパイル時間 | 1,170 ms |
コンパイル使用メモリ | 99,616 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-17 17:09:52 |
合計ジャッジ時間 | 2,249 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <iostream> #include <numeric> #include <string> #include <vector> using namespace std; #include <atcoder/modint> using mint = atcoder::modint998244353; vector<vector<mint>> ncr; vector<mint> pow2; mint solve(int N, int K, string X) { vector<mint> dp(N + 1); dp[N] = 1; // dp[# of candidate elements] for (auto c : X) { vector<mint> dpnxt(dp.size()); const bool x = (c == '1'); for (int i = K; i <= N; ++i) { for (int j = 0; j <= i; ++j) { if (x) { // j : # of 1 if (i - j < K) dpnxt[i] += dp[i] * pow2[N - i] * ncr[i][j]; } if (!x) { // j : # of 0 if (j >= K) dpnxt[j] += dp[i] * pow2[N - i] * ncr[i][j]; } } } dp = dpnxt; } return accumulate(dp.begin(), dp.end(), mint(0)); } int main() { int N, M, K; string X; cin >> N >> M >> K >> X; ncr.assign(201, vector<mint>(201)); for (int i = 0; i < int(ncr.size()); ++i) ncr[i][0] = 1; for (int i = 1; i < int(ncr.size()); ++i) { for (int j = 1; j < int(ncr[i].size()); ++j) ncr[i][j] = ncr[i - 1][j - 1] + ncr[i - 1][j]; } pow2.assign(201, 1); for (int i = 1; i < int(pow2.size()); ++i) pow2[i] = pow2[i - 1] * 2; cout << solve(N, K, X).val() << '\n'; }