結果
問題 | No.2833 Count Taiko Results |
ユーザー |
👑 ![]() |
提出日時 | 2024-08-03 00:15:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 59 ms / 2,000 ms |
コード長 | 1,731 bytes |
コンパイル時間 | 2,053 ms |
コンパイル使用メモリ | 203,072 KB |
最終ジャッジ日時 | 2025-02-23 20:38:19 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 58 |
ソースコード
#line 1 "era.cpp"#include <bits/stdc++.h>#include <atcoder/modint>#line 4 "/Users/Shared/po167_library/ds/Swag.hpp"namespace po167{template<class T, T (*op)(T, T), T (*e)()>struct SWAG{std::vector<std::pair<T, T>> A, B;SWAG(int n = -1){if (n > 0) A.reserve(n + 1), B.reserve(n + 1);A.push_back({e(), e()});B.push_back({e(), e()});}void push(T v){B.push_back({v, op(B.back().second, v)});}void pop(){if ((int)A.size() == 1){while ((int)B.size() != 1){A.push_back({B.back().first, op(B.back().first, A.back().second)});B.pop_back();}}assert((int)A.size() != 1);A.pop_back();}T calc(){return op(A.back().second, B.back().second);}};}#line 4 "era.cpp"using mint = atcoder::modint998244353;using namespace std;mint op(mint a, mint b){return a * b;}mint e(){return 1;}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;auto f = [&](int k) -> mint {po167::SWAG<mint, op, e> S(k + 1);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.calc();S.pop();}if (i == N) break;S.push(A[i]);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";}