提交时间:2022-10-04 11:27:26
运行 ID: 57473
#include <bits/stdc++.h> using namespace std; const int maxn=100010,mod=998244353; int sum[21][maxn],dp[21][maxn],n,x,y; int main() { // freopen("J3.in","r",stdin); // freopen("J3.out","w",stdout); scanf("%d%d%d",&n,&x,&y); dp[0][0]=1; for(int i=0; i<=x; i++) sum[0][i]=1;//维护前缀和 即 [1~j-1] for(int i=1; i<=20; i++) for(int j=1; j<=x; j++) { // for(int k=1; k<=j; k++) // if(k!=y) (dp[i][j]+=dp[i-1][j-k])%=mod; dp[i][j]=sum[i-1][j/2]; if(j>n) dp[i][j]=(dp[i][j]-sum[i-1][j-n-1]+mod)%mod; if(y>=j-j/2 && y<=j) dp[i][j]=(dp[i][j]-dp[i-1][j-y]+mod)%mod; sum[i][j]=(sum[i][j-1]+dp[i][j])%mod; } int ans=0; for(int i=1; i<=20; i++) (ans+=dp[i][x])%=mod; printf("%d\n",ans); return 0; }//n \lg n //dp_{i,j} i 件 重量为 j 的方案数 //ans=dp_{k,x} (1 \le k \le x) //dp_{i,j}=\sum_{i=1}^{k}dp_{i-1,j-k} (j\ge k and k!=y) //\sum_{i=1}^{k}dp_{i-1,j-k}(j\ge k and k!=y) -> ans(1,j)-dp_{i-1,j-y} //100000 100000 100000