結果
問題 | No.2215 Slide Subset Sum |
ユーザー |
![]() |
提出日時 | 2023-04-27 22:55:16 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,218 ms / 3,000 ms |
コード長 | 1,808 bytes |
コンパイル時間 | 2,366 ms |
コンパイル使用メモリ | 207,204 KB |
最終ジャッジ日時 | 2025-02-12 14:31:10 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 45 |
ソースコード
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int mod = 998244353; typedef tuple<int,int,int> T; ll answer(vector<ll> &a, vector<ll> &b, int k){ ll ret = 0; for (int i=0; i<k; i++){ ret += a[i] * b[(k-i) % k]; ret %= mod; } return ret; } vector<ll> addone(vector<ll> &a, int x, int k){ vector<ll> ret = a; for (int i=0; i<k; i++){ ret[(i+x)%k] += a[i]; ret[(i+x)%k] %= mod; } return ret; } void calc(int l, int r, int mid, int k, vector<int> &a, vector<T> &q, vector<ll> &ans, vector<vector<ll>> &dp){ dp[mid] = vector<ll>(k); dp[mid][0] = 1; for (int i=mid-1; i>=l; i--){ dp[i] = addone(dp[i+1], a[i], k); } for (int i=mid+1; i<=r; i++){ dp[i] = addone(dp[i-1], a[i-1], k); } for (auto [ind, l, r]: q){ ans[ind] = (answer(dp[l], dp[r], k) - 1 + mod) % mod; } } void gogo(int l, int r, int k, vector<int> &a, vector<T> &q, vector<ll> &ans, vector<vector<ll>> &dp){ if (r-l <= 1){ for (auto [ind, l, r]: q){ if (a[l] == 0) ans[ind] = (ll)1; else ans[ind] = (ll)0; } return; } int mid = (l + r) / 2; vector<T> gocalc, lquery, rquery; for (auto [ind, l, r]: q){ if (mid <= l) rquery.push_back(make_tuple(ind, l, r)); else if (r <= mid) lquery.push_back(make_tuple(ind, l, r)); else gocalc.push_back(make_tuple(ind, l, r)); } calc(l, r, mid, k, a, gocalc, ans, dp); gogo(l, mid, k, a, lquery, ans, dp); gogo(mid, r, k, a, rquery, ans, dp); return; } int main(){ int n, m, k; cin >> n >> m >> k; vector<int> a(n); vector<vector<ll>> dp(n+1, vector<ll>(k)); for (int i=0; i<n; i++){ cin >> a[i]; } int qnum = n-m+1; vector<T> q(qnum); vector<ll> ans(qnum); for (int i=0; i<qnum; i++){ q[i] = make_tuple(i, i, i+m); } gogo(0, n, k, a, q, ans, dp); for (int i=0; i<qnum; i++){ cout << ans[i] << "\n"; } }