結果
問題 | No.2215 Slide Subset Sum |
ユーザー |
|
提出日時 | 2023-02-12 02:10:59 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 206 ms / 3,000 ms |
コード長 | 1,475 bytes |
コンパイル時間 | 2,425 ms |
コンパイル使用メモリ | 193,672 KB |
最終ジャッジ日時 | 2025-02-10 14:38:01 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 45 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll=long long; using pii=pair<int,int>; #define all(a) a.begin(),a.end() #define pb push_back #define sz(a) ((int)a.size()) const int maxn=200005,mod=998244353; int add(int x, int y){x+=y; if(x>=mod) x-=mod; return x;} int sub(int x, int y){x-=y; if(x<0) x+=mod; return x;} int mul(int x, int y){return ((ll)x)*y%mod;} int n,m,k,a[maxn],dp[2][maxn][105]; signed main(){ ios_base::sync_with_stdio(0),cin.tie(0); cin >> n >> m >> k; for(int i=0; i<n; ++i) cin >> a[i]; for(int i=0; i<n; ++i){ if(i%m==0){ dp[0][i][0]=1; dp[0][i][a[i]]=add(dp[0][i][a[i]],1); continue; } int cur=k-a[i]; if(cur==k) cur=0; for(int j=0; j<k; ++j) dp[0][i][j]=add(dp[0][i-1][j],dp[0][i-1][cur]),cur=(cur+1==k?0:cur+1); } for(int i=n-1; i>=0; --i){ if(i%m==m-1||i==n-1){ dp[1][i][0]=1; dp[1][i][a[i]]=add(dp[1][i][a[i]],1); continue; } int cur=k-a[i]; if(cur==k) cur=0; for(int j=0; j<k; ++j) dp[1][i][j]=add(dp[1][i+1][j],dp[1][i+1][cur]),cur=(cur+1==k?0:cur+1); } for(int i=0; i+m<=n; ++i){ if(i%m==0) cout << sub(dp[0][i+m-1][0],1) << "\n"; else{ int res=sub(mul(dp[0][i+m-1][0],dp[1][i][0]),1); for(int j=1; j<k; ++j) res=add(res,mul(dp[0][i+m-1][j],dp[1][i][k-j])); cout << res << "\n"; } } }