https://atcoder.jp/contests/arc104/tasks

C - Fair Elevator

 

题意：在 1 到 2n 的数轴上给定 nn 个区间，定义一组合法的区间集合：所有端点恰被使用一次，交叉的区间长度必须相同。给定的区间中有 -1 表示数据缺失，问给定的区间集合是否有可能为合法的区间集合。

区间dp

合法区间的形式显然是如上图这样的。要么是能分成左右两部分都是合法区间，要么自己是一个最小的合法区间。

最小的合法区间：区间长度为偶数，且左半区间只有左端点，右半部分只有右端点，且所有区间长度都为总长度的一半。

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define debug(x) cout << #x << ":\t" << x << endl;
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
int n;
int a[N], b[N];
int dp[1010][1010], vis[1010];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int l, r;
		scanf("%d%d", &l, &r);
		if (l != -1 && r != -1 && r <= l) { puts("No"); return 0; }
		if (l != -1) {
			if (vis[l]) { puts("No"); return 0; }
			a[l] = r;
			vis[l] = 1;
		}
		if (r != -1) {
			if (vis[r]) { puts("No"); return 0; }
			b[r] = l;
			vis[r] = 1;
		}
	}
	n <<= 1;
	for (int len = 2; len <= n; len += 2) {
		for (int i = 1; i <= n - len + 1; i++) {
			int j = i + len - 1;
			for (int k = i; k < j; k++) {
				if (dp[i][k] && dp[k + 1][j]) {
					dp[i][j] = 1;
					break;
				}
			}
			if (dp[i][j])continue;
			dp[i][j] = 1;
			for (int k = i; k <= i + len / 2 - 1; k++) {
				if (b[k])dp[i][j] = 0;
				if (a[k]) {
					if (a[k] != -1 && a[k] - k != len / 2)dp[i][j] = 0;
					else {
						if (b[k + len / 2] && b[k + len / 2] != k)dp[i][j] = 0;
					}
				}
			}
			for (int k = i + len / 2; k <= j; k++) {
				if (a[k])dp[i][j] = 0;
				if (b[k]) {
					if (b[k] != -1 && k - b[k] != len / 2)dp[i][j] = 0;
					else {
						if (a[k - len / 2] && a[k - len / 2] != k)dp[i][j] = 0;
					}
				}
			}
		}
	}
	puts(dp[1][n] ? "Yes" : "No");
	return 0;
}

 

D - Multiset Mean

 

题意：给定n，k，1 到 n 每个数可以选 0 到 k 次，对于 1≤x≤n1\le x\le n，求凑出集合，集合均值为 x 的方案数。

dp

均值显然需要转化。

∑ai∈Sai=x⇓∑ai∈S(ai−x)=0⇓∑ai∈S,x<ai≤n(ai−x)=∑aj∈S,1≤aj<x(x−aj)\sum_{a_i\in S}a_i=x\\ \Downarrow\\ \sum_{a_i\in S}(a_i-x)=0\\ \Downarrow\\ \sum_{a_i\in S,x<a_i\le n}(a_i-x)=\sum_{a_j\in S,1\le a_j<x}(x-a_j)\\

所以就是要选出一些数，和相等。可以看到左侧 ai−x∈[1,n−x]a_i-x\in[1,n-x]，右侧 x−aj∈[1,x−1]x-a_j\in [1,x-1]。

dp[i][j]dp[i][j] 表示用 1 到 i，和为 j 的方案数。

枚举和 s，把 dp[n−x][s]⋅dp[x−1][s]dp[n-x][s]\cdot dp[x-1][s] 计入答案。

下面考虑怎么计算dp。

dp[i][j]=∑k=0Kdp[i−1][j−ki]dp[i][j]=\sum_{k=0}^Kdp[i-1][j-ki]\\

如果没有 k≤Kk\le K 这个限制的话，dp[i][j]=∑dp[i−1][j−ki]dp[i][j]=\sum dp[i-1][j-ki]，也就是等于所有与 jj 模 ii 同余的 dp 之和。所以可以维护一个ps[]，记录模 ii 同余的等价类的 dp 值之和。dp[i][j]=ps[j%i]dp[i][j]=ps[j\%i]。

而有了 k≤Kk\le K，则还需要一个大小为 K 的滑动窗口，每次当 j≥Kij\ge Ki 时窗口下端收缩。

复杂度 O(n3K)O(n^3K)

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
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n, K;
int m;
int dp[110][1000010];
ll ps[110];
int main() {
	scanf("%d%d%d", &n, &K, &m);
	dp[0][0] = 1;
	int s = 0;
	for (int i = 1; i <= n; i++) {
		fill(ps, ps + i, 0);
		s += i;
		for (int j = 0; j <= s * K; j++) {
			int x = j % i;
			ps[x] = (ps[x] + dp[i - 1][j]) % m;
			if (j - i * (K + 1) >= 0)ps[x] = (ps[x] + m - dp[i - 1][j - i * (K + 1)]) % m;
			dp[i][j] = ps[x];
		}
	}
	s = 0;
	for (int x = 1; x <= n; x++) {
		ll ans = 0;
		s += x;
		for (int i = 0; i <= s * K; i++) {
			ans = (ans + 1ll * dp[n - x][i] * dp[x - 1][i] % m) % m;
		}
		ans = (ans*(K + 1) - 1 + m) % m; 
		printf("%lld\n", ans);
	}
	return 0;
}