QOJ6408 Classical Counting Problem 题解

First Post:

Last Update:

本题的思考过程称不上难，但比较曲折。

设全集为 。

枚举集合 ，集合 能被生成的条件是存在一种加的方式，使得最后有 。

分两种情况讨论：

  1. 。

    此时我们肯定会让所有加分都加到 中的点，所以 不会改变，假设已经知道了 ，那么对于 ，设 。那么操作变为每次给 个 减去 ，问能否使得操作 次后所有 都不超过 。

    定理：能操作成功当且仅当 且 。

    证明：必要性显然。

    充分性：设 表示 的个数，当 时显然可以删完。对于 的情况考虑数学归纳，我们只需证明操作一次之后 且 。 部分是显然的。 部分，如果原先的最大值就 那无需讨论，否则， 的位置显然不会超过 个，将这些位置选中即可使得 减少 。

    所以，我们将 从小到大排序，枚举 表示 中最大的元素，那么 后面的元素都在 中且 均为 。对于 前面的元素，考虑背包 DP。设 表示 DP 到第 个元素，当前选入 中的元素最小值为 ，个数为 ，总和为 ，在 处枚举合法的 DP 值加上贡献即可。这是 的。

    注意到 那一维只是用来判断 的，用处并不大，所以考虑双指针，设 表示最小的满足 的位置，我们只需维护选区间 中元素的背包即可。在 增加时，我们需要撤销一个元素在背包中的贡献。这只需将加入背包时的循环倒过来做即可。

  2. ，这种情况实质上是选 中的 个元素减去 ，与上一种情况是本质相同的。

于是这题就做完了，时间复杂度 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 5,M = 1e4 + 5,P = 998244353;
inline void Plus(int &x,const int &y) { x += y;if(x >= P) x -= P;}
int n,m,V;
int a[N];
int W;
int dp[N][M];

inline void Addw(int x,int y) {
	for(int i = n;i >= x;i--)
		for(int j = W;j >= y;j--)
			Plus(dp[i][j],dp[i - x][j - y]);
}
inline void Delw(int x,int y) {
	for(int i = x;i <= n;i++)
		for(int j = y;j <= W;j++)
			Plus(dp[i][j],P - dp[i - x][j - y]);
}

inline int Solve1() {// |S| >= V 
	for(int i = 0;i <= n;i++) for(int j = 0;j <= W;j++) dp[i][j] = 0;
	dp[0][0] = 1;int ans = 0;
	for(int r = 1,l = 1;r <= n;r++) { // 最大的 U \ S，r 后面的不用管 
		while(l <= r - 1 && a[r] - a[l] > m)
			Delw(1,a[l]),++l;
		for(int sz = max(0,V - (n - r));sz <= n;++sz)
			for(int i = max(0,sz * a[r] - V * m);i <= W;i++)
				Plus(ans,dp[sz][i]);
		Addw(1,a[r]);
	}
	return ans;
}
inline int Solve2() { // |S| < v,|U\S| > n - V
	// U\S 里选 n - V 个减 1，枚举 min(S)
	for(int i = 0;i <= n;i++) for(int j = 0;j <= W;j++) dp[i][j] = 0;
	dp[0][0] = 1;int ans = 0;
	for(int l = n,r = n;l >= 1;l--) {
		while(r > l && a[r] - a[l] > m) 
			Delw(1,a[r]),--r;
		for(int sz = max(0,n - V + 1 - (l - 1));sz <= n;++sz)
			for(int i = 0;i <= min(W,(n - V) * m + sz * a[l]);i++)
				Plus(ans,dp[sz][i]);
		Addw(1,a[l]);
	}
	return ans;
}

inline void work() {
	cin >> n >> m >> V;
	W = 0;
	for(int i = 1;i <= n;i++) cin >> a[i],W += a[i];
	sort(a + 1,a + n + 1);
	int ans = Solve1();
	Plus(ans,Solve2());
	cout << (ans + 1) % P << endl; // 加上选全集的方案
}
int main() {
	int T;
	cin >> T;
	while(T--) work();
	return 0;
}
/*
6
3 1 2
1 2 3
3 2 1
1 2 3
10 1 1
0 0 0 0 0 0 0 0 0 0
6 1 2
2 1 1 3 0 2
6 1 5
2 1 1 3 0 2
10 4 8
7 2 3 6 1 6 5 4 6 5
*/
≡