因为第N个人的作用仅仅是丰富题面，可以直接把N减1。C的作用仅仅是为了使情景更逼真，可以直接把L和R减去C。显然选的人的个数最多是的。题目中有个条件，保证了想要选的数的总和不会超过N。考虑类似于背包的dp。令dp[i][j]表示现在已经选了最大的i个想选的数，和为j时的方案数。转移的时候，要么把之前选择的每一个数增加一，要么在把之前选择的每一个数都增加一个基础上，再新加入一个当前大小为1的数。若最后选的个数为i，，那么就对答案产生的贡献。累加即可。注意一个都不选也是合法的。复杂度.PS：解释下转移方程，由于选的值是不能重复，直接用背包肯定超时，这里就用了一个巧妙的方法，移位，将i 个数右移1位，即每个数都增加1，即是dp[i][j+i],右移一位后最前面会空出1位，这时在最前面增加一个数 1，因为经过移位，所有的数都比1大，所以不会出现重复，即dp[i+1][j+i+1].代码：#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>using namespace std;const int maxn=100000+100;const int mod= 998244353;const int maxm=450;int dp[2][maxn+5];int s[maxn+5];int main(){int t,n;dp[1][1]=1;int it=1;//滚动数组标记for(int i=1; i<=maxm; i++,it=!it){for(int j=1; j<=maxn; j++){if(j+i<=maxn)dp[it][j+i]=(dp[it][j+i]+dp[it][j])%mod;if(j+i+1<=maxn)dp[!it][j+i+1]=(dp[it][j]+dp[!it][j+i+1])%mod;s[j]=(s[j]+dp[it][j])%mod;//取的值为j的和dp[it][j]=0;//为下一行初始化}}for (int j = 1; j < maxn; j++)//前缀和s[j] = (s[j] + s[j – 1]) % mod;scanf("%d",&t);while(t–){scanf("%d",&n);int c,l,r;scanf("%d%d%d",&c,&l,&r);r=r-c;l=l-c;int ans=s[r];if(l>0)ans=(ans-s[l-1]+mod)%mod;if(l==0)//全部不取时ans++;printf("%d\n",ans);}return 0;}
使用双手头脑与心灵的是艺术家，只有合作双手
