多校省选模拟1

A

题意

定义一个长度为 \(n\) 的序列是好的，当且仅当有一个子段是 \(k\) 的排列。问所有长度为 \(n\)，值域为 \(k\) 的彩色序列中，序列中一个长度为 \(m\) 的序列 \(A\) 一共出现了多少次。对于 \(1e9+7\) 取模。

\(1\le n \le 25000,1\le k\le 400\)。

题解

我们考虑正难则反，考虑计算出不管序列好不好，出现了多少次 \(A\)，然后减去不好的 \(A\) 中出现的次数即可。

那么前面的答案是 \((n-m+1)k^{n-m}\)，然后我们考虑怎么算出来后面这个答案。

首先，如果 \(A\) 本身就是好的数列，那么，后面那个部分肯定是 \(0\)。

有一个部分分是算 \(A\) 里边的数互不相同的，我们只要算出来对于任意的 \(A\) 出现多少次，然后除以 \(k^{\underline m}\) 即可。

我们称一个序列是 \(\text{diff}\) 的，当且仅当它的数各不相同。预处理出来 \(F[i][j]\) 表示长度为 \(i\) 且不好的序列，结尾恰有一个极长为 \(j\) 的序列的个数。我们可以注意到，这种情况下，其实对于 \(\text{diff}\) 序列是怎么样的，他们的方案数都是一样的。

我们可以得到 \(F[1][1] = k\)，然后递推公式为 \(F[i][j] = (k - j + 1)F[i - 1][j-1]+\sum_{l\ge j}F[i-1][j]\)。这个不难看出来。

也就是说，我们对于某个特定的长度 \(j\) 的 \(\text{diff}\) 序列，所有长度为 \(i\) 的不好的序列的方案数 \(G[i][j]\) 以它结尾的方案数是 \(\frac{\sum_{l=j}^{k-1}F[i][l]}{k^{\underline j}}\)。

那么，这也就启发了，我们要对于 \(A\) 是不是 \(\text{diff}\) 序列进行讨论，这样就不会有一个 \(k\) 排列跨越 \(A\) 了。

我们其次在考虑 \(A\) 是个互不相同的情况，该怎么计算答案。

我们枚举这个 \(A\) 的开头位置 \(i\)，然后枚举这个序列的前 \(i+m-1\) 位置结尾最长的 \(\text{diff}\) 序列的长度 \(j\)（这个的字符串的方案数是 \(\frac{F[i+m-1][j]}{k^{\underline m}}\)），然后从这个 \(\text{diff}\) 序列的开头位置 \(pos\) 来乘上一个 \(G[m-pos+1][j]\) 即可。

那么，我们在考虑 \(A\) 有相同数字的情况，我们就只要把这个东西分成两段，然后分别用 \(G\) 计算即可。

#include <bits/stdc++.h>
using std::cin;
using std::cout;
const int MAXK = 405, MAXN = 2.5e4 + 10, MOD = 1e9 + 7;
int N, M, K, A[MAXN], F[MAXN][MAXK], S[MAXN][MAXK], lst[MAXK];
long long sig[MAXK];
auto Ksm = [] (long long x, int y) -> long long {
	long long ret = 1;
	for (; y; y >>= 1, x = x * x % MOD) {
		if (y & 1) {
			ret = ret * x % MOD;
		}
	}
	return ret;
};
int main() {
	freopen("sequence.in", "r", stdin);
	freopen("sequence.out", "w", stdout);
	std::ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> K >> M;
	sig[0] = 1;
	for (int i = 1; i <= K; ++i) {
		sig[i] = sig[i - 1] * (K - i + 1) % MOD;
	}
	for (int i = 1; i <= K; ++i) {
		sig[i] = Ksm(sig[i], MOD - 2);
	}
	F[1][1] = S[1][1] = K;
	for (int i = 2; i <= N; ++i) {
		for (int j = 1; j < K; ++j) {
			F[i][j] = (F[i - 1][j - 1] * (K - j + 1LL) + S[i - 1][j]) % MOD;
		}
		for (int j = K - 1; j; --j) {
			S[i][j] = (S[i][j + 1] + F[i][j]) % MOD;
		}
	}
	for (int i = 1; i <= M; ++i) {
		cin >> A[i];
	}
	int ANS = Ksm(K, N - M) * (N - M + 1) % MOD, l = 1;
	for (int i = 1; i <= M; ++i) {
		if (lst[A[i]] >= l) {
			l = lst[A[i]] + 1;
		}
		lst[A[i]] = i;
		if (i - l + 1 >= K) {
			cout << ANS << '\n';
			return 0;
		}
	}
	if (l != 1) {
		// 有相同的 再找一个 r
		memset(lst, 63, sizeof lst);
		int r = M;
		for (int i = M; i; --i) {
			if (lst[A[i]] <= r) {
				r = lst[A[i]] - 1;
			}
			lst[A[i]] = i;
		}
		auto solve2 = [&] (int n, int m, int L, int R) -> int {
			int ret = 0;
			for (int i = 1; i <= n - m + 1; ++i) {
				ret = (ret + 1LL * S[i + L - 1][L] * S[n - i - m + 1 + R][R]) % MOD;
			}
			return 1LL * ret * sig[L] % MOD * sig[R] % MOD;
		};
		cout << (ANS - solve2(N, M, r, M - l + 1) + MOD) % MOD << '\n';
	}
	else {
		auto solve1 = [&] (int n, int m, int k) -> int {
			int ret = 0;
			for (int i = 1; i <= n - m + 1; ++i) {
				for (int j = m; j < std::min(i + m, k); ++j) {
					ret = (ret + 1LL * F[i + m - 1][j] * S[n - i - m + 1 + j][j] % MOD * sig[j]) % MOD;
				}
			}
			return 1LL * ret * sig[m] % MOD;
		};
		cout << (ANS - solve1(N, M, K) + MOD) % MOD << '\n';
	}
	return 0;
}

再来说一下神 Cirno_9 的对于 \(A\) 互不相同的神做法：

首先 \(F\) 数组是一样的。然后我们考虑直接去计算一个数组 \(C[i][j]\) 表示，一个长度为 \(i\) 的序列，序列末尾有一个极长为 \(j\) 的 \(\text{diff}\) 序列的出现了长度为 \(m\) 的互不相同的数字的组数。

那么，我们可以得到 \(C[i][j] = (k - j + 1)C[i-1][j - 1]+\sum_{l\ge j} C[i - 1][l] + [j\ge m] dp[i][j]\)

然后我们发现 \(\frac{\sum _{l}C[n][l]}{k^{\underline m}}\) 就是答案了。

B

题意

给你一个有 \(n\) 个点，\(m\) 条边的有向图，一个节点是好的，当且仅当这个节点到其他节点都是只有一条路径的。保证给你的图里面有趣的节点个数的百分比不少于 \(20\%\)，求所有这样有趣的节点。

题解

这种百分比的东西，启发我们需要随机化。

我们先考虑怎么找到一个有趣的点，我们只要对这个点做 \(\text{dfs}\)，然后如果没有横叉边和重孙边，那么这就是对的。

那么，我们随机100次肯定可以找到一个有趣的点。

我们找到了这个有趣的点，以这个点建立 \(\text{dfs}\) 树，满足这棵树上只有可能返租边和树边。那么，我们考虑，如果有两个返租边跨越一个节点，那么肯定有这个节点是不合法的。

否则，假定我们可以通过 \(x\) 子树内的返祖边到达上方的顶点是个 \(u\)，那么如果 \(u\) 不好，\(x\) 肯定也不好，因为这必定是上一种情况，或者说还可以在 \(u\) 的子树内向上爬升为 \(v\)，那么最上方的那个顶点肯定也是不合法的。

#include <bits/stdc++.h>
const int MAXN = 1e5 + 10;
using std::cin;
using std::cout;
using std::vector;
int T, N, M;
vector<int> e[MAXN];
int vis[MAXN], inst, ck[MAXN], cnt[MAXN], anc[MAXN], dep[MAXN];
long long rnd() {
	return (((long long) rand()) << 26) | rand();
}
void dfs(int nw) {
	vis[nw] = 1;
	for (auto &j: e[nw]) {
		if (!vis[j]) {
			dfs(j);
		}
		else if (vis[j] == 2) {
			inst = 0;
		}
	}
	vis[nw] = 2;
}
int Dfs(int nw) {
	vis[nw] = 1;
	anc[nw] = nw;
	for (auto &j: e[nw]) {
		if (!vis[j]) {
			dep[j] = dep[nw] + 1;
			cnt[nw] += Dfs(j);
			if (dep[anc[nw]] > dep[anc[j]]) {
				anc[nw] = anc[j];
			}
		}
		else {
			--cnt[j];
			++cnt[nw];
			if (dep[j] < dep[anc[nw]]) {
				anc[nw] = j;
			}
		}
	}
	if (cnt[nw] > 1) {
		ck[nw] = 1;
	}
	return cnt[nw];
}
void Dfs2(int nw) {
	vis[nw] = 1;
	ck[nw] |= ck[anc[nw]];
	for (auto &j: e[nw]) {
		if (!vis[j]) {
			Dfs2(j);
		}
	}
	return;
}
void solve() {
	cin >> N >> M;
	for (int i = 1; i <= N; ++i) {
		e[i].clear();
	}
	for (int i = 1, x, y; i <= M; ++i) {
		cin >> x >> y;
		e[x].push_back(y);
	}
	int id = -1;
	for (int i = 1; i <= 100; ++i) {
		int r = rnd() % N + 1;
		auto check = [&] () -> int {
			memset(vis, 0, 4 * (N + 1));
			inst = 1;
			dfs(r);
			return inst;
		};
		if (check()) {
			id = r;
			break;
		}
	}
	assert(id != -1);
	memset(vis, 0, 4 * (N + 1));
	memset(ck, 0, 4 * (N + 1));
	memset(cnt, 0, 4 * (N + 1));
	dep[0] = -1;
	Dfs(id);
	memset(vis, 0, 4 * (N + 1));
	Dfs2(id);
	for (int i = 1; i <= N; ++i) {
		if (!ck[i]) {
			cout << i << ' ';
		}
	}
	cout << '\n';
	return;
}
int main() {
	freopen("graph.in", "r", stdin);
	freopen("graph.out", "w", stdout);
	srand(20050112);
	std::ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	for (cin >> T; T--; ) {
		solve();
	}
	return 0;
}

C

题意

给你 \(n\) 个向量 \((x,y)\)，然后你可以用这些向量来构成一个凸多边形，要满足这个多边形能放在一个 \(m\times m\) 的一个正方形里边。

求有多少种方案可以构成这个凸多边形，对于 \(998244353\) 取模

题解

我们考虑，由于构成的就是个凸多边形，所以每个向量的顺序，其实在你选定这些向量的时候，就定下来了。那么我们只要求，有多少种选定向量的个数就可以了。

也就是说，我们要求这个 \(c\) 序列的方案树，满足 \(\sum_{i=1}^nc_ix_i=0,\sum_{i=1}^nc_iy_i=0,\sum_{i=1}^nc_ix_i[x_i>0]\le m,\sum_{i=1}^nc_iy_i[y_i>0]\le m\) 。

然后这个题就开始奇怪的技巧了。我们的 \(dp\) 要保证我们的正的 \(c_ix_i\) 的和比 \(m\) 小，\(y\) 同理，负的也同理，同时最后要满足加的正的数字要等于负的数字。然后这就类似于数位 \(dp\)。我们按照每次根据二进制位来做，每次转移这些 \(c_i\) 的第 \(i\) 位是不是 \(0/1\)，设 \(f[i][cpx][cpy][cnx][cny][bx][by]\) 为我们做到第 \(i\) 位，然后前 \(i\) 位里我们有 \(x\) 轴上正的进位为 \(cpx\)，负的进位为 \(cnx\)，有 \(y\) 轴上正的进位为 \(cpy\)，负的进位为 \(cny\)，\(bx\) 为前 \(i\) 位里 \(x\) 和 \(m\) 相比的大小关系，\(by\) 为前 \(i\) 位里 \(y\) 和 \(m\) 的大小关系。

然后每次，我们转移这些 \(c\) 的第 \(i\) 个二进制位，然后，这些 \(c_i\) 就会改变状态，然后转移到 \(f[i+1]\) 上。

这个进位是什么意思，就是说，我们不是会加一些 \(c_i[bit(c_i,k)]x_i\) 吗，然后这些会给总的 \(\sum c_ix_i\) 做贡献，然后就是这玩意会记录和 \(m\) 的大小关系即可。

最后我们要的答案就是 \(dp[30][0][0][0][0][0][0]-1\)（要减去什么都不选的方案）。

这个进位的数组大小大概开20就够了，因为每次最多加 \(20\)，除以二就是 \(10\)，然后相当于是

#include <bits/stdc++.h>
const int MOD = 998244353;
using std::cin;
using std::cout;
auto Mod = [] (int x) -> int {
	if (x >= MOD) {
		return x - MOD;
	}
	else if (x < 0) {
		return x + MOD;
	}
	else {
		return x;
	}
};
int x[5], y[5], px[32], py[32], nx[32], ny[32], dp[31][20][20][20][20][2][2];
int main() {
	freopen("shape.in", "r", stdin);
	freopen("shape.out", "w", stdout);
	std::ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int N, M;
	cin >> N >> M;
	for (int i = 0; i < N; ++i) {
		cin >> x[i] >> y[i];
	}
	int limit = 1 << N;
	for (int mask = 0; mask < limit; ++mask) {
		for (int i = 0; i < N; ++i) {
			if ((mask >> i) & 1) {
				if (x[i] > 0) {
					px[mask] += x[i];
				}
				else {
					nx[mask] += x[i];
				}
				if (y[i] > 0) {
					py[mask] += y[i];
				}
				else {
					ny[mask] += y[i];
				}
			}
		}
		nx[mask] = -nx[mask];
		ny[mask] = -ny[mask];
	}
	dp[0][0][0][0][0][0][0] = 1;
	for (int i = 0; i < 30; ++i) {
		for (int cpx = 0; cpx < 20; ++cpx) {
			for (int cpy = 0; cpy < 20; ++cpy) {
				for (int cnx = 0; cnx < 20; ++cnx) {
					for (int cny = 0; cny < 20; ++cny) {
						for (int bx = 0; bx < 2; ++bx) {
							for (int by = 0; by < 2; ++by) {
								if (!dp[i][cpx][cpy][cnx][cny][bx][by]) {
									continue;
								}
								for (int mask = 0; mask < limit; ++mask) {
									int npx = cpx + px[mask], npy = cpy + py[mask], nnx = cnx + nx[mask], nny = cny + ny[mask];
									if ((npx ^ nnx) & 1 || (npy ^ nny) & 1) {
										continue;
									}
									int cx = npx & 1, mx = (M >> i) & 1, cy = npy & 1, my = (M >> i) & 1;
									dp[i + 1][npx >> 1][npy >> 1][nnx >> 1][nny >> 1][cx != mx ? cx > mx : bx][cy != my ? cy > my : by] = Mod(dp[i + 1][npx >> 1][npy >> 1][nnx >> 1][nny >> 1][cx != mx ? cx > mx : bx][cy != my ? cy > my : by] + dp[i][cpx][cpy][cnx][cny][bx][by]);
								}
							}
						}
					}
				}
			}
		}
	}
	cout << Mod(dp[30][0][0][0][0][0][0] - 1) << '\n';
	return 0;
}