結果
問題 |
No.1533 Don't be Negative!
|
ユーザー |
|
提出日時 | 2022-07-02 18:36:48 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,310 bytes |
コンパイル時間 | 373 ms |
コンパイル使用メモリ | 45,368 KB |
実行使用メモリ | 10,276 KB |
最終ジャッジ日時 | 2024-11-27 14:20:47 |
合計ジャッジ時間 | 303,957 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 25 TLE * 28 |
ソースコード
#include <cstdio> #include <cstring> #include <algorithm> const int Maxn=80000; const int Mod=998244353; const int inv_2=(Mod+1)/2; int f[2][Maxn+6]; int n,m,k; int pow_v[Maxn+5]; int main(){ scanf("%d%d%d",&n,&m,&k); int cur=0,nxt; f[cur][0]=1; pow_v[0]=1; for(int i=1;i<=n;i++){ pow_v[i]=1ll*pow_v[i-1]*(2*m-1+(k==0))%Mod; } int ans=0; for(int i=1;i<=n;i++){ nxt=cur^1; int cur_len=std::min(i-1,n-i+1)*m,nxt_len=std::min(i,n-i)*m; int sum=0; for(int j=0;j<=nxt_len;j++){ sum=(sum+f[cur][j])%Mod; if(j-m-1>=0){ sum=(sum-f[cur][j-m-1]+Mod)%Mod; } f[nxt][j]=sum; if(j-k>=0){ f[nxt][j]=(f[nxt][j]-f[cur][j-k]+Mod)%Mod; } } sum=0; for(int j=cur_len;j>=-m;j--){ if((k==0&&j+1>=0)||j+1>0){ sum=(sum+f[cur][j+1])%Mod; } if(j+m+1<=cur_len){ sum=(sum-f[cur][j+m+1]+Mod)%Mod; } int nxt_j=std::abs(j); if(nxt_j<=nxt_len){ f[nxt][nxt_j]=(f[nxt][nxt_j]+sum)%Mod; if(k>0&&j+k>0&&std::abs(j+k)<=cur_len){ f[nxt][nxt_j]=(f[nxt][nxt_j]-f[cur][std::abs(j+k)]+Mod)%Mod; } } } if(k!=0){ f[nxt][0]=(2ll*f[nxt][0]-f[cur][0]+Mod)%Mod; } memset(f[cur],0,(cur_len+1)*sizeof(int)); cur=nxt; int val=1ll*(pow_v[i]-f[cur][0]+Mod)*inv_2%Mod; ans=(ans+1ll*pow_v[n-i]*val%Mod*(n-i+1))%Mod; } printf("%d\n",ans); return 0; }