【题目来源】https://acm.hdu.edu.cn/showproblem.php?pid7239【题目描述】zyb 在访问莫斯科期间购买了 n 个 matryoshka 玩偶大小分别为 a1、a2、…、an从最小到最大排序。大小为 i 的 matryoshka 可以放入另一个大小为 j 的 matryoshka当且仅当 j−i≥r、 其中r是某个给定的整数参数。zyb 希望将所有 n 个 matryoshka 玩偶分成 k 组这样每个组中都可以形成一个嵌套的 Matryoshka 玩偶其中一组 Matryoska 玩偶的索引为 c1、c2、…、cm1≤c1c2…cm≤n 可以形成嵌套的 matryoshka 玩偶如果 ∀1≤ima[ci]r≤a[ci1]。zyb 想知道有多少种方法可以将 n 个玩偶分成 k 组以满足上述要求。请注意诸如 {{1,2}, {3,4}} 和 {{3,4}, {1,2}} 等划分被视为相同的方式。由于答案可能太大您只需要输出答案模 998244353。【输入格式】第一行包含整数T1≤T≤20 表示测试用例的数量。对于每个测试用例第一行包含三个整数 nkr1≤k≤n≤5000,1≤r≤1e9表示 matryoshka 玩偶的数量zyb 想要划分的组的数量以及参数。下一行包含 n 个整数 a1、a2、…、an1≤a1≤a2≤...≤an≤1e9表示 matryoshka 玩偶的尺寸。可以保证 ∑n≤所有测试用例中有 50000 个。【输出格式】对于每个测试用例在一行中输出一个整数表示取模 998244353 的答案。​​​​​​​【输入样例】24 3 21 2 3 44 2 11 1 2 2【输出样例】32【数据范围】1≤T≤201≤k≤n≤5000,1≤r≤1e91≤a1≤a2≤...≤an≤1e9【算法分析】有 n 个套娃大小为 a1 ≤a2 ≤... ≤an现在要将这些套娃分成 k 组每组套娃按照大小排序后相邻两个套娃之间的大小差距要求r求方案数。设f[i][j] 表示将前 i 个套娃分成 j 组的方案数状态转移方程为f[i][j]f[i-1][j-1](新增一组) f[i-1][j]*max(0, j-num(z)) (第 x 的套娃跟之前的放在一组)其中 num(z) 表示 1zi 且ai-razai 的 z 的个数。时间复杂度为O(n^2)。【算法代码】HDUhttps://acm.hdu.edu.cn/ 不支持万能头文件。#include iostream #include algorithm using namespace std; typedef long long LL; const int M5005; const LL mod998244353; int n,k,r,a[M]; LL f[M][M]; int main() { int T; scanf(%d,T); while(T--) { scanf(%d%d%d,n,k,r); for(int i1; in; i) scanf(%d,a[i]); for(int i0; in; i) { for(int j0; jk; j) f[i][j]0; } f[0][0]1; for(int i1,z1; in; i) { while(zi a[i]-ra[z]) z; int numi-z; for(int jnum1; jmin(i,k); j) { f[i][j](f[i-1][j-1]f[i-1][j]*(j-num))%mod; } } printf(%lld\n,f[n][k]); } return 0; } /* in: 2 4 3 2 1 2 3 4 4 2 1 1 1 2 2 out: 3 2 */【参考文献】https://acm.hdu.edu.cn/showproblem.php?pid7239https://mp.weixin.qq.com/s/HNISXyopgpO1PmATouxuyg