http://acm.hdu.edu.cn/showproblem.php?pid=5230
把题目简化后，就是求
1---n - 1这些数字中，将其进行整数划分，其中整数划分中不能有重复的数字，如果有这样的划分并且那个数字在[L, R]区间中，那么就算做一个贡献。
以前的整数划分，一般就是dp[i][j]表示i这个数字，最小的拆分数是j的时候，拥有的方案数，可以控制其没有重复数字，但是空间复杂度太大。
用一种新的方法
dp[i][j]表示j这个数字，当前的拆分拥有i个拆分数时的方案数。至于为什么要在第二维中放j这个数字，而不是像上面那个用第一维放数字，那是因为它需要先解出dp[1][1---n]然后再解出dp[2][1---n]，转换维度比较方便。
先考虑允许重复数字 ： dp[i][j] = dp[i][j - i] + dp[i - 1][j - 1];
考虑分成两类，
1、dp[i][j - i]：这种拆分方案（拥有i个数字的拆分方案），如果没有1，就比如7 = 3 + 4这样，然后每个数字都加上一，
就变成了9 = 5 + 4。所以dp[2][9]可以由dp[2][7]转化过来。当然7 = 1 + 6也是合法解。
2、dp[i - 1][j - 1]：这种拆分方案有1，比如4 = 3 + 1，那么我可以截去那个1，变成3 = 3，然后加上最后那个1，就变成了
4 = 3 + 1，所以dp[2][4]可以由dp[1][3]转化过来。
但是题目需要不重复，（这也使得题目不会超时）
第一类，如果dp[2][7]本来就是不重复的，就是dp[2][6]即是6 = 3 + 3不能发生，那么我同时全部加上一个数，肯定不会产生重复
的。
第二类，如果本来也是不重复的，但是生成的可能会重复，比如5 = 4 + 1和5 = 3 + 2是dp[2][5]的解（本来没有重复），然后在后面加上一个1，是dp[3][6]的解，但是6 = 4 + 1 + 1是非法的。我们也不可能检查其拆分方案有没1，因为我们只会统计数量。
改进
dp[i][j] = dp[i][j - i] + dp[i - 1][j - i];
dp[i - 1][j - i]：意思就是每个元素减去1后，分成i - 1组，为什么不是分成i组呢。？因为其存在1，然后每个数字减去1,那么这个1就是变成0了，所以只能分成i - 1组。
例如：6 = 3 + 2 + 1是由3 = 2 + 1弄过来的，dp[3][6] = dp[2][3]
所以就能解决这题。
1、i > j，不用管dp[i][j] = 0
2、i == j，只能够是i个1,然而不符合题目，dp[i][j] = 0;
3、i < j，dp[i][j] = dp[i][j - i] + dp[i - 1][j - i];
由于之和上一维有关，可以滚动数组，就能解决空间问题。
然后因为要产生k个不同的数字，最小值是1 + 2 + 3 + ..... + k，就是(1 + k) * k / 2开始。
就是dp[2][2]这些不用枚举了，k = 2的话，最小值是3
初始条件 dp[0][0] = 1;
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> const int MOD = 998244353; const int maxn = 100000 + 20; int dp[2][maxn]; void work() { int n, c, L, R; scanf("%d%d%d%d", &n, &c, &L, &R); if (c > R) { printf("0 "); return; } L = L - c; R = R - c; int ans = L == 0; //c自己是一个 memset(dp, 0, sizeof dp); dp[0][0] = 1; int now = 0; int all = 0; for (int i = 1; i <= R; ++i) { //枚举拆分成i个，最多拆分成(i + 1) * i / 2个。 if (i * (i + 1) / 2 > R) break; //超越分数了 for (int j = (i + 1) * i / 2; j <= R; ++j) { dp[now][j] = (dp[now][j - i] + dp[!now][j - i]) % MOD; if (j >= L && j <= R) { ans += dp[now][j]; ans %= MOD; } } memset(dp[!now], 0, sizeof dp[!now]); now = !now; } printf("%d ", ans); } int main() { #ifdef local freopen("data.txt","r",stdin); #endif int t; scanf("%d", &t); while (t--) work(); return 0; }