6

「专题选做」简单计数题选做 1

 2 years ago
source link: https://blunt-axe.github.io/2019/12/03/20191203-Easy-Counting-1/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

SetAndSet

「Topcoder 12004」SetAndSet

给 个数 ，要把它们划分成两个集合，使得两边的 And 一样，问方案数。

数据范围：。

也就是说对于每一位，如果存在一个数这一位为 ，那么这一位为 的数不能全在同一边。考虑容斥，每次强制某些位让这一位为 的数全在同一边。使用并查集维护即可，直接实现时间复杂度 ，容斥用 dfs 实现复杂度为 ，可以通过（忽略并查集复杂度）。

#include <bits/stdc++.h>
2
using namespace std;
3
4
typedef long long ll;
5
const int maxn = 50, maxm = 20;
6
7
class SetAndSet {
8
public:
9
	int n, a[maxn + 3], fa[maxm + 3][maxn + 3];
	vector<int> S[maxm + 3];
	bool vis[maxn + 3];
	ll ans;
	int find(int i, int x) {
		return fa[i][x] == x ? x : fa[i][x] = find(i, fa[i][x]);
	}
	void dfs(int i, int x) {
		if (i == maxm) {
20
			for (int j = 1; j <= n; j++) {
21
				vis[j] = false;
22
			}
23
			for (int j = 1; j <= n; j++) {
24
				vis[find(i, j)] = true;
25
			}
26
			ll y = 1;
27
			for (int j = 1; j <= n; j++) {
28
				if (vis[j]) y <<= 1;
29
			}
30
			ans += x * (y - 2);
31
			return;
32
		}
33
		memcpy(fa[i + 1], fa[i], sizeof(fa[i]));
34
		dfs(i + 1, x);
35
		if (!S[i].empty()) {
36
			memcpy(fa[i + 1], fa[i], sizeof(fa[i]));
37
			for (int j = 0; j < S[i].size() - 1; j++) {
38
				fa[i + 1][find(i + 1, S[i][j])] = find(i + 1, S[i][j + 1]);
39
			}
40
			dfs(i + 1, -x);
41
		}
42
	}
43
44
	ll countandset(vector<int> A) {
45
		n = A.size();
46
		for (int i = 1; i <= n; i++) {
47
			a[i] = A[i - 1];
48
			for (int j = 0; j < maxm; j++) {
49
				if (~a[i] >> j & 1) {
50
					S[j].push_back(i);
51
				}
52
			}
53
		}
54
		for (int i = 1; i <= n; i++) {
55
			fa[0][i] = i;
56
		}
57
		ans = 0;
58
		dfs(0, 1);
59
		return ans;
60
	}
61
};

Endless Spin

「HDU 4624」Endless Spin

有 个格子，每次随机选择一个区间染黑，问全染黑的期望时间。答案保留 位小数。

数据范围：。

我们要求的是 ，其中 表示第 个格子被覆盖的时间。考虑 Min-Max 容斥，计算 。对于某个 ，我们要算出经过 种某个点的区间个数 ，设总区间个数为 ，那么它对答案的贡献是容斥系数乘上 。带上容斥系数套个 dp 即可，由于精度要求较高可以使用高精度 / int128，时间复杂度 。

#include <bits/stdc++.h>
2
using namespace std;
3
4
typedef long long ll;
5
typedef __int128 lll;
6
typedef double db;
7
const int maxn = 50, maxm = maxn * (maxn + 1) >> 1;
8
const ll inf = 1e18;
9
ll dp[maxn + 3][maxm + 3], f[maxn + 3][maxm + 3];
lll ans[maxn + 3];
int T;
inline int func(const int &x) {
	return x * (x + 1) >> 1;
}
int main() {
	for (int i = 1; i <= maxn; i++) {
		dp[i][func(i - 1)] = 1;
20
		for (int j = 1; j < i; j++) {
21
			for (int k = 0; k <= func(j - 1); k++) {
22
				dp[i][func(i - j - 1) + k] -= dp[j][k];
23
			}
24
		}
25
	}
26
	for (int i = 1; i <= maxn; i++) {
27
		for (int j = 1; j <= i; j++) {
28
			for (int k = 0; k <= func(j - 1); k++) {
29
				f[i][func(i - j) + k] += dp[j][k];
30
			}
31
		}
32
	}
33
	for (int i = 1; i <= maxn; i++) {
34
		for (int j = 0; j <= func(i - 1); j++) {
35
			ans[i] += (lll) f[i][j] * func(i) * inf / (func(i) - j);
36
		}
37
	}
38
	scanf("%d", &T);
39
	for (int n; T --> 0; ) {
40
		scanf("%d", &n);
41
		printf("%d.%015lld\n", (int) (ans[n] / inf), ((ll) (ans[n] % inf) + 500) / 1000);
42
	}
43
	return 0;
44
}

随机立方体

「CTS 2019」随机立方体（Luogu 5400）

有 的立方体，每个位置有 范围内随机的实数，一个数是极大的当且仅当它大于任何一个与它某一维坐标相同的数。问恰好有 个极大的数的概率。

数据范围：。

记 ，以及钦定 个数极大，其他随便选的概率的和为 ，那么根据二项式反演，答案等于：

我们考虑 怎么求。首先从小到大钦定 个数，之后我们会得到一棵表示大小关系的树：

上图是二维时 的情况，两个极大值分别是 和 ，一个格子指向另一个格子表示一个格子大于另一个格子。根据经典结论，概率应该是子树大小的倒数相乘，所以最终的式子是：

直接计算即可，注意要用到线性求逆元，时间复杂度 。

#include <bits/stdc++.h>
2
using namespace std;
3
4
const int maxn = 5e6, mod = 998244353;
5
int T, n, m, l, k, N, fact[maxn + 3], finv[maxn + 3], a[maxn + 3];
6
7
int qpow(int a, int b) {
8
	int c = 1;
9
	for (; b; b >>= 1, a = 1ll * a * a % mod) {
		if (b & 1) c = 1ll * a * c % mod;
	}
	return c;
}
void prework(int n) {
	fact[0] = 1;
	for (int i = 1; i <= n; i++) {
		fact[i] = 1ll * fact[i - 1] * i % mod;
	}
20
	finv[n] = qpow(fact[n], mod - 2);
21
	for (int i = n; i; i--) {
22
		finv[i - 1] = 1ll * finv[i] * i % mod;
23
	}
24
}
25
26
int C(int n, int m) {
27
	return 1ll * fact[n] * finv[m] % mod * finv[n - m] % mod;
28
}
29
30
void solve(int a[], int n) {
31
	int prod = 1;
32
	for (int i = 1; i <= n; i++) {
33
		prod = 1ll * prod * a[i] % mod;
34
	}
35
	int inv = qpow(prod, mod - 2);
36
	for (int i = n, x; i; i--) {
37
		x = a[i], a[i] = inv;
38
		inv = 1ll * inv * x % mod;
39
	}
40
}
41
42
int main() {
43
	prework(maxn);
44
	scanf("%d", &T);
45
	while (T --> 0) {
46
		scanf("%d %d %d %d", &n, &m, &l, &k);
47
		N = min(n, min(m, l));
48
		for (int i = 1; i <= N; i++) {
49
			a[i] = (1ll * n * m % mod * l - 1ll * (n - i) * (m - i) % mod * (l - i)) % mod;
50
			a[i] < 0 ? a[i] += mod : 0;
51
		}
52
		solve(a, N);
53
		int cur = 1;
54
		for (int i = 1; i < k; i++) {
55
			cur = 1ll * cur * (n - i + 1) % mod * (m - i + 1) % mod * (l - i + 1) % mod;
56
		}
57
		int ans = 0;
58
		for (int i = k; i <= N; i++) {
59
			cur = 1ll * cur * (n - i + 1) % mod * (m - i + 1) % mod * (l - i + 1) % mod;
60
			ans = (ans + 1ll * C(i, k) * ((i - k) & 1 ? -1 : 1) * cur % mod * a[i]) % mod;
61
		}
62
		ans < 0 ? ans += mod : 0;
63
		printf("%d\n", ans);
64
	}
65
	return 0;
66
}

Square Constraints

「AGC 036F」Square Constraints

求有多少个 的排列 ，满足 。

数据范围：。

考虑子问题：长度为 的排列 有多少个满足 。考虑先把 从小到大排序，根据乘法原理，方案数就是 。

注意到这个做法是基于 的大小排名的。考虑原题，发现限制的形状如下：

阴影部分是 可以选的地方，空白部分是不能选的地方。我们考虑容斥，把前 个限制拆成 。考虑把所有限制分成三类：A 类，B 类和 C 类。我们把所有限制按照高度从小到大排序，得到的序列一定长成这样：。在序列中，我们要选择所有的 C，以及第 个 A 和第 个 B 中的一个。额外地，每选到一个 A 后，系数就要乘上 。

考虑 dp 前 个字符， 表示考虑前 个字符，A 选了 个的方案数。对于一个 A / C，我们容易计算它的排名，但是对于一个 A 对应的 B，我们就不能得到它的排名了。于是，我们考虑事先枚举要用 个 A，然后再 dp，这样就可以得到 B 的排名。这样我们就得到了一个时间复杂度为 的做法。

#include <bits/stdc++.h>
2
#define fi first
3
#define se second
4
using namespace std;
5
6
const int maxn = 500;
7
int n, mod, L[maxn + 3], R[maxn + 3], dp[maxn + 3][maxn + 3];
8
pair<int, int> a[maxn + 3];
9
int get(int x, int y) {
	int z = 0;
	while (z < n * 2 - 1 && (z + 1) * (z + 1) + x <= y) {
		z++;
	}
	return z;
}
int solve(int k) {
	memset(dp, 0, sizeof(dp));
20
	dp[0][0] = 1;
21
	int A = 0, C = 0;
22
	for (int i = 0; i < n * 2; i++) {
23
		if (~a[i].se) {
24
			for (int j = 0; j <= A; j++) {
25
				dp[i + 1][j + 1] = (dp[i + 1][j + 1] + 1ll * dp[i][j] * (a[i].fi - j - C)) % mod;
26
			}
27
			for (int j = 0; j <= A; j++) {
28
				dp[i + 1][j] = (dp[i + 1][j] + 1ll * dp[i][j] * (a[i].se - k - n - (A - j))) % mod;
29
			}
30
			A++;
31
		} else {
32
			for (int j = 0; j <= A; j++) {
33
				dp[i + 1][j] = (dp[i + 1][j] + 1ll * dp[i][j] * (a[i].fi - j - C)) % mod;
34
			}
35
			C++;
36
		}
37
	}
38
	return dp[n * 2][k];
39
}
40
41
int main() {
42
	scanf("%d %d", &n, &mod);
43
	for (int i = 0; i < n; i++) {
44
		a[i] = make_pair(get(i * i, n * n - 1) + 1, get(i * i, n * n * 4) + 1);
45
	}
46
	for (int i = n; i < n * 2; i++) {
47
		a[i] = make_pair(get(i * i, n * n * 4) + 1, -1);
48
	}
49
	sort(a, a + n * 2);
50
	int ans = 0;
51
	for (int i = 0; i <= n; i++) {
52
		ans = (ans + 1ll * (i & 1 ? mod - 1 : 1) * solve(i)) % mod;
53
	}
54
	printf("%d\n", ans);
55
	return 0;
56
}

HamiltonianPaths

「Topcoder 14250」HamiltonianPaths

给定一个 个点的图，把它复制 边，然后取补图，问新图的哈密尔顿路径条数，对 取模。

数据范围：。

也就是说限制整个完全图中不能经过 条边。考虑容斥，枚举必须经过 条边，那么对答案的贡献就是 乘上方案数。假设一个子图里经过了 条不合法边，组成了 条有向的链，那么将链定向后，对答案的贡献就是 ，也就是说权值为 。最后如果缩点后还剩 个点，方案数就是 。所以要算出每个图缩成 个点的权值和，然后用 fft 求出大图缩成 个点的权值和。一个子图的权值和可以通过简单状压 dp 实现，总时间复杂度 。

#include <bits/stdc++.h>
2
using namespace std;
3
4
const int maxn = 14, maxk = 1 << maxn, maxm = 1 << 20, mod = 998244353;
5
6
class HamiltonianPaths {
7
public:
8
	bool a[maxn + 3][maxn + 3];
9
	int n, k, dp[maxk + 3][maxn + 3], cnt[maxk + 3], f[maxk + 3][maxn + 3];
	int g[maxm + 3], h[maxm + 3], g_n, h_n, lim, bit, rev[maxm + 3], A[maxm + 3], B[maxm + 3];
	inline int func(const int &x) {
		return x < mod ? x : x - mod;
	}
	int qpow(int a, int b) {
		b < 0 ? b += mod - 1 : 0;
		int c = 1;
		for (; b; b >>= 1, a = 1ll * a * a % mod) {
20
			if (b & 1) c = 1ll * a * c % mod;
21
		}
22
		return c;
23
	}
24
25
	void dft(int a[], int n, int type) {
26
		for (int i = 0; i < n; i++) {
27
			if (i < rev[i]) swap(a[i], a[rev[i]]);
28
		}
29
		for (int k = 1; k < n; k <<= 1) {
30
			int x = qpow(3, (mod - 1) / (k << 1) * type);
31
			for (int i = 0; i < n; i += k << 1) {
32
				int y = 1;
33
				for (int j = i; j < i + k; j++, y = 1ll * x * y % mod) {
34
					int p = a[j], q = 1ll * a[j + k] * y % mod;
35
					a[j] = func(p + q), a[j + k] = func(p - q + mod);
36
				}
37
			}
38
		}
39
		if (type == -1) {
40
			int x = qpow(n, mod - 2);
41
			for (int i = 0; i < n; i++) {
42
				a[i] = 1ll * a[i] * x % mod;
43
			}
44
		}
45
	}
46
47
	void mult(int a[], int &n, int b[], int m) {
48
		for (lim = 1, bit = 0; lim <= n + m; lim <<= 1) bit++;
49
		for (int i = 1; i < lim; i++) {
50
			rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
51
		}
52
		for (int i = 0; i <= n; i++) {
53
			A[i] = a[i];
54
		}
55
		for (int i = 0; i <= m; i++) {
56
			B[i] = b[i];
57
		}
58
		fill(A + n + 1, A + lim, 0);
59
		fill(B + m + 1, B + lim, 0);
60
		dft(A, lim, 1), dft(B, lim, 1);
61
		for (int i = 0; i < lim; i++) {
62
			A[i] = 1ll * A[i] * B[i] % mod;
63
		}
64
		dft(A, lim, -1);
65
		n += m;
66
		for (int i = 0; i <= n; i++) {
67
			a[i] = A[i];
68
		}
69
	}
70
71
	int countPaths(int N, vector<int> A, vector<int> B, int K) {
72
		n = N, k = K;
73
		for (int i = 0; i < A.size(); i++) {
74
			a[A[i] + 1][B[i] + 1] = true;
75
			a[B[i] + 1][A[i] + 1] = true;
76
		}
77
		for (int i = 1; i <= n; i++) {
78
			dp[1 << (i - 1)][i] = 1;
79
		}
80
		for (int msk = 1; msk < 1 << n; msk++) {
81
			for (int i = 1; i <= n; i++) if (dp[msk][i]) {
82
				for (int j = 1; j <= n; j++) if (a[i][j] && (~msk >> (j - 1) & 1)) {
83
					dp[msk | (1 << (j - 1))][j] = func(dp[msk | (1 << (j - 1))][j] - dp[msk][i] + mod);
84
				}
85
			}
86
			for (int i = 1; i <= n; i++) if (dp[msk][i]) {
87
				cnt[msk] = func(cnt[msk] + dp[msk][i]);
88
			}
89
		}
90
		f[0][0] = 1;
91
		for (int msk = 1; msk < 1 << n; msk++) {
92
			int p = 0;
93
			for (int i = 1; i <= n; i++) {
94
				if (msk >> (i - 1) & 1) {
95
					p = i;
96
					break;
97
				}
98
			}
99
			int t = msk ^ (1 << (p - 1));
			for (int k = 0; k < n; k++) {
				f[msk][k + 1] = f[t][k];
			}
			for (int i = t; i; i = (i - 1) & t) {
				for (int k = 0; k < n; k++) {
					f[msk][k + 1] = (f[msk][k + 1] + 1ll * cnt[i | (1 << (p - 1))] * f[msk ^ (i | 1 << (p - 1))][k]) % mod;
				}
			}
		}
		for (int i = 1; i <= n; i++) {
			g[i] = f[(1 << n) - 1][i];
		}
		h[0] = 1;
		int g_n = n, h_n = 0;
		for (int i = k; i; i >>= 1, mult(g, g_n, g, g_n)) {
			if (i & 1) mult(h, h_n, g, g_n);
		}
		int cur = 1, ret = 0;
		for (int i = 1; i <= n * k; i++) {
			cur = 1ll * cur * i % mod;
			ret = (ret + 1ll * h[i] * cur) % mod;
		}
		return ret;
	}
};

Fireflies

「HDU 6355」Fireflies

给定 个数 ，令 ，问有多少 元组 满足：

数据范围：，至多两组数据满足 。

注意：此题中的 定义为 ，所以 时的组合数也可以计算。

考虑容斥， 的方案数为 。考虑将强制大于 的数减去 ，然后使用插板法，问题就转化成了计算：

直接计算不行，考虑折半搜索。使用范德蒙德恒等式：

用到这题里就是：

那么我们左边、右边分别预处理组合数，然后 2 - pointers 合并即可。时间复杂度 。

#include <bits/stdc++.h>
2
using namespace std;
3
4
typedef long long ll;
5
const int maxn = 32, maxm = 1 << (maxn >> 1), mod = 1e9 + 7;
6
int T, n, A, B, k, l, p[maxn + 3], inv[maxn + 3], s[maxn + 3];
7
ll m;
8
9
struct thing {
	ll fi;
	int se[maxn + 3];
	friend bool operator < (const thing &a, const thing &b) {
		return a.fi < b.fi;
	}
} a[maxm + 3], b[maxm + 3];
inline int func(const int &x) {
	return x < mod ? x : x - mod;
}
20
21
void prework(int n) {
22
	inv[1] = 1;
23
	for (int i = 2; i <= n; i++) {
24
		inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
25
	}
26
}
27
28
int main() {
29
	prework(maxn);
30
	scanf("%d", &T);
31
	while (T --> 0) {
32
		scanf("%d", &n);
33
		ll sum = 0;
34
		for (int i = 1; i <= n; i++) {
35
			scanf("%d", &p[i]);
36
			sum += p[i] + 1;
37
		}
38
		m = (sum >> 1);
39
		A = n >> 1, B = n - A;
40
		k = l = 0;
41
		int ans = 0;
42
		for (int msk = 0; msk < 1 << A; msk++) {
43
			int y = 1;
44
			ll z = 0;
45
			for (int i = 1; i <= A; i++) {
46
				if (msk >> (i - 1) & 1) {
47
					y = mod - y, z += p[i];
48
				}
49
			}
50
			a[++k].fi = m - 1 - z;
51
			int x = func((m - 1 - z) % mod + mod);
52
			a[k].se[0] = y;
53
			for (int i = 1; i < n; i++) {
54
				a[k].se[i] = 1ll * a[k].se[i - 1] * (x - i + 1 + mod) % mod * inv[i] % mod;
55
			}
56
		}
57
		for (int msk = 0; msk < 1 << B; msk++) {
58
			int y = 1;
59
			ll z = 0;
60
			for (int i = 1; i <= B; i++) {
61
				if (msk >> (i - 1) & 1) {
62
					y = mod - y, z += p[i + A];
63
				}
64
			}
65
			b[++l].fi = -z;
66
			int x = func((-z) % mod + mod);
67
			b[l].se[0] = y;
68
			for (int i = 1; i < n; i++) {
69
				b[l].se[i] = 1ll * b[l].se[i - 1] * (x - i + 1 + mod) % mod * inv[i] % mod;
70
			}
71
		}
72
		sort(a + 1, a + k + 1);
73
		sort(b + 1, b + l + 1);
74
		int p = l;
75
		for (int i = 0; i < n; i++) {
76
			s[i] = 0;
77
		}
78
		for (int i = 1; i <= k; i++) {
79
			while (p && a[i].fi + b[p].fi >= 0) {
80
				for (int j = 0; j < n; j++) {
81
					s[j] = func(s[j] + b[p].se[j]);
82
				}
83
				p--;
84
			}
85
			for (int j = 0; j < n; j++) {
86
				ans = (ans + 1ll * a[i].se[j] * s[n - j - 1]) % mod;
87
			}
88
		}
89
		printf("%d\n", ans);
90
	}
91
	return 0;
92
}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK