結果
問題 | No.2215 Slide Subset Sum |
ユーザー |
|
提出日時 | 2023-02-11 06:20:54 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 703 ms / 3,000 ms |
コード長 | 1,423 bytes |
コンパイル時間 | 1,801 ms |
コンパイル使用メモリ | 180,420 KB |
実行使用メモリ | 168,704 KB |
最終ジャッジ日時 | 2024-07-07 22:20:32 |
合計ジャッジ時間 | 19,007 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 45 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using Vl = std::vector<ll> ; ll const m = 998244353; std::stack<Vl> st1, st2; stack<int> stt; int N, M, K; void Push(int a, int id = 1) { stack<Vl>& S = (id ? st2 : st1); Vl A(K, 0); if (S.empty()) { A[0] = 1; A[a] ++; } else { auto B = S.top(); for (int i = 0; i < K; i ++) { A[i] = B[i] + B[(i + K - a) % K]; A[i] %= m; } } S.push(A); if (id == 1) { stt.push(a); } } void Pop() { if (!st1.empty()) { st1.pop(); } else { while (!st2.empty()) { auto v = st2.top(); st2.pop(); auto a = stt.top(); stt.pop(); Push(a, 0); } st1.pop(); } } void CA() { Vl A(K, 0), B(K, 0); if (st1.empty()) { A[0] = 1; } else { A = st1.top(); } if (st2.empty()) { B[0] = 1; } else { B = st2.top(); } ll ans = m - 1; for (int i = 0; i < K; i ++) { ans += (A[i] * B[(K - i) % K]) % m; ans %= m; } cout << ans << endl; } int main () { cin >> N >> M >> K; for (int i = 0; i < M - 1; i ++) { int a; cin >> a; Push(a); } for (int i = M - 1; i < N; i ++) { int a; cin >> a; Push(a); CA(); Pop(); } }