先对一个数来看，注意到拆成的每个正整数只能用一次，也就是100000内的数最多拆成400+个
然后来寻找递推，dp[i][j]表示j拆成i个数的方案，这个时候可以i个数都加1，或者新增一个1，问题来了，不能确定原来i个是否有1，所以再开一维[0/1]表示i个数有没有1
得到递推式：
dp[i][j][0]表示最小数不为1，dp[i][j][1]表示最小数为1
1 add(dp[i][j+i][0],dp[i][j][0]+dp[i][j][1]);2 add(dp[i+1][j+1][1],dp[i][j][0]);
这样就会得到MLE，再加一个滚动数组即可AC本题
1 #include2 #include 3 #include 4 #define MOD 998244353 5 using namespace std; 6 int Now[101005][2],Next[101005][2],s[101005]; 7 void add(int &x,int y) 8 { 9 if (y>MOD) y-=MOD;10 x+=y;11 if (x>MOD) x-=MOD;12 } 13 int main()14 {15 int i,j,T,c,n,l,r;16 memset(s,0,sizeof(s));17 Next[1][1]=1;18 for (i=1;i<=450;i++)19 {20 for (j=1;j<=100000;j++) 21 {22 Now[j][0]=Next[j][0]; Next[j][0]=0;23 Now[j][1]=Next[j][1]; Next[j][1]=0;24 }25 for (j=i;j<=100000;j++)26 {27 add(Now[j+i][0],Now[j][0]+Now[j][1]);28 add(Next[j+1][1],Now[j][0]);29 }30 for (j=1;j<=100000;j++) add(s[j],Now[j][0]+Now[j][1]);31 }32 s[0]=1;33 for (i=1;i<=100000;i++) add(s[i],s[i-1]);34 scanf("%d",&T);35 while (T--)36 {37 scanf("%d%d%d%d",&n,&c,&l,&r);38 l-=c; r-=c; c=s[r];39 if (l!=0) c=s[r]-s[l-1];40 if (c<0) c+=MOD;41 printf("%d\n",c);42 }43 return 0;44 }
题目链接：