結果
問題 | No.2833 Count Taiko Results |
ユーザー |
👑 ![]() |
提出日時 | 2024-08-03 00:18:50 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 77 ms / 2,000 ms |
コード長 | 963 bytes |
コンパイル時間 | 1,933 ms |
コンパイル使用メモリ | 200,528 KB |
最終ジャッジ日時 | 2025-02-23 20:38:38 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 58 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/modint> using mint = atcoder::modint998244353; using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N, K; cin >> N >> K; vector<int> A(N), B(N); for (auto &a : A) cin >> a; for (auto &b : B) cin >> b; vector<mint> S(N + 1, 1), Si(N + 1); for (int i = 0; i < N; i++) S[i + 1] = S[i] * A[i]; Si[N] = S[N].inv(); for (int i = N; i > 0; i--) Si[i - 1] = Si[i] * A[i - 1]; auto f = [&](int k) -> mint { std::vector<mint> dp0(N + 1), dp1(N + 1); dp1[0] = 1; for (int i = 0; i <= N; i++){ if (k <= i){ dp0[i] -= dp1[i - k] * S[i] * Si[i - k]; } if (i == N) break; dp0[i + 1] += (dp0[i] + dp1[i]) * A[i]; dp1[i + 1] += (dp0[i] + dp1[i]) * B[i]; } return dp0[N] + dp1[N]; }; cout << (f(K + 1) - f(K)).val() << "\n"; }