[dp]Matryoshka Doll 2022杭电多校第9场 1007

Problem Description

zyb bought nn matryoshka dolls during his visit to Moscow, with sizes a1,a2,…,ana1​,a2​,…,an​, respectively, sorting from smallest to largest.

A matryoshka of size ii can be put into another matryoshka of size jj if and only if j−i≥rj−i≥r, where rr is some given integer parameter.

zyb wishes to divide all nn matryoshka dolls into kk groups, such that one can form a nestedmatryoshka doll in each group, where a group of matryoshka dolls with indices c1,c2,...,cmc1​,c2​,...,cm​ (1≤c1nested matryoshka doll iff ∀1≤i

zyb wants to know how many ways there are to divide the nn dolls into kk groups satisfying the requirement above. Note that divisions such as 1,2,3,41,2,3,4 and 3,4,1,23,4,1,2 are considered the same way. As the answer may be too large, you only need to output the answer modulo 998244353998244353.

Input

The first line contains an integer T(1≤T≤20)T(1≤T≤20), denoting the number of test cases.

For each test case, the first line contains three integers n,k,r(1≤k≤n≤5000,1≤r≤109)n,k,r(1≤k≤n≤5000,1≤r≤109), denoting the number of matryoshka dolls, the number of groups zyb wants to divide into, and the parameter, respectively.

The next line contains nn integers a1,a2,…,an(1≤a1≤a2≤...≤an≤109)a1​,a2​,…,an​(1≤a1​≤a2​≤...≤an​≤109), denoting the sizes of the matryoshka dolls. 

It is guaranteed that ∑n≤50000∑n≤50000 over all test cases.

Output

For each test case, output an integer in a line, denoting the answer taken modulo 998244353998244353.

Sample Input

2

4 3 2

1 2 3 4

4 2 1

1 1 2 2

Sample Output

3

2

题意： 有n个玩偶，它们的尺寸分别为ai，当两玩偶尺寸差大于等于r时就可以把两个玩偶套起来，问将这n个玩偶分成k组的方案数，要求每组的玩偶都能够套起来。

分析： 设dp[i][j]表示将前i个玩偶分成j组的方案数，初始状态dp[i][i] = 1，状态转移时dp[i][j]由两部分构成，一部分是当前这个玩偶自成一组的情况，这部分的方案数显然是dp[i-1][j-1]，另一部分是当前这个玩偶套在之前各组玩偶身上的情况，这部分的方案数需要考虑前面j组中各组的最大值，如果当前这个玩偶的尺寸能套在各组最大的那个玩偶上，那方案数就加一，其实无论前面分了几组，不管每组是怎么分的，当前这个玩偶能套在几个组上是固定的，可以稍微证明下，只需要知道每个组的最大值中有几个在(ai-r, ai]范围内就得证，而在(ai-r, ai]范围内的玩偶一定是组内的最大值，否则会找到一个比ai还大的玩偶，这肯定是不存在的情况，那也就可以从前面的i-1个玩偶中遍历，找出有多少个玩偶是在(ai-r, ai]范围内的，用分组数j一减就是能套上的组数，这一部分的方案数也就是dp[i-1][j]*(j-num[i])，num[i]就是前i-1个玩偶有多少是在(ai-r, ai]范围内的，这可以通过O(n^2)暴力求出。

具体代码如下：

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
 
int dp[5005][5005], a[5005], num[5005];
const int mod = 998244353;
 
signed main()
{
	int T;
	cin >> T;
	while(T--){
		int n, k, r;
		scanf("%d%d%d", &n, &k, &r);
		for(int i = 1; i <= n; i++){
			scanf("%d", &a[i]);
			num[i] = 0;
		}
		for(int i = 1; i <= n; i++)
			for(int j = 1; j < i; j++)
				if(a[j] > a[i]-r)
					num[i]++;
		for(int i = 1; i <= n; i++) dp[i][i] = 1;
		for(int i = 1; i <= n; i++)
			for(int j = 1; j < i; j++){
				dp[i][j] = (dp[i-1][j-1]+1ll*dp[i-1][j]*(j-num[i]))%mod;
			}
	
		printf("%d\n", dp[n][k]);
	}
    return 0;
}