結果
問題 | No.2833 Count Taiko Results |
ユーザー |
👑 ![]() |
提出日時 | 2024-08-03 00:18:05 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 962 bytes |
コンパイル時間 | 1,773 ms |
コンパイル使用メモリ | 200,792 KB |
最終ジャッジ日時 | 2025-02-23 20:38:28 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 6 WA * 52 |
ソースコード
#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] * S[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";}