多校省选模拟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\)，然后相当于是
\[10+5+\cdots+\frac{1}{2^k}<20 \]#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;
}