happyguy round, god round
2023省选模拟 happyguy round
T1 游戏
贪心题。首先可以观察到两个性质：
- \(a_1, a_n\) 肯定最后取；
- 若 \(a_{i - 1} > a_{i} < a_{i + 1}\)，那么肯定先取 \(a_i\) 更优。
那么我们可以贪心地选取第二种情况，最后会形成一个单峰的形式，单峰形式贪心显然，每次取最大值即可。
T2 专家
有趣的构造题。
这种题肯定是考虑类似于二进制的方式进行构造。
我们考虑先连出一个三元环 \(1 - 2 - 3\)，这个三元环的染色方案为 \(6\)。我们可以假设颜色涂的为 \(1,2,3\)，最后方案数乘 \(6\) 即可。
接下来我们选 \(8\) 个点，其中第一个点连 \(3\)，第二个点连 \(1\)，第三个点连 \(2\)，第四个点连 \(3\)，依次类推。那么我们发现，第一个点可以选的颜色有 \((1, 2)\)，第二个点可以选的颜色有 \((2, 3)\)，等等。
我们再把这几个点连成一条链，这样我们发现，这条链上存在一个前缀都选前者的颜色，一个后缀都选后者的颜色。此时染色的方案数为 \(9\)。
我们考虑在 \(i\) 个点下面连 \(a_i\) 个点，并且这 \(a_i\) 个点都连向 \(i\) 点的前者的颜色。这样，如果这个点选前者的颜色，那么这个点有两种选择方案，否则只有一种选择方案。
那么我们假设一个 \(j\) 的前缀选前者，那么方案数就是 \(2^{a_1 + a_2 + \cdots + a_j}\)。那么我们总方案数就是 \(2^0 + 2^{a_1} + 2^{a_1 + a_2} + \cdots\)。
对于没有用到的点，我们可以先把 \(i\) 号点钦定选右边，这样可以将前缀的位置限制住，剩下的点连 \(1, 2\) 就行。
此时奇数的答案已经可以构造了。对于偶数来说，我们可以在 \(1\) 下面挂几个叶子，每个叶子的方案数为 \(2\)。
T3 平衡
首先打表可以发现，如果出现了 \(a\) 个 \(0\)，那么答案为一个串重复 \(\gcd(n, a)\) 次，那么不同的循环位移得到的合法串有 \(\frac{n}{\gcd(n, a)}\) 个。那么我们先只考虑重复的一次，较大的子串容易归纳至仅重复一次的子串。将 \(n, a\) 均除以 \(\gcd(n, a)\) 后，我们有 \(\gcd(n, a) = 1\)。
那么我们猜测，对于一个固定的 \(a\)，合法的串在循环同构的意义下是唯一的。那么我们尝试来找出这个串。
我们尝试用权值来刻画这个 \(01\) 序列。假如我们给 \(0,1\) 定一个权值，令一个子串的权值为 \(0, 1\) 的权值和。由于我们存在循环子串，我们希望使得这个权值序列的和为 \(0\)，这样所有跨过边界的子串的权值可以用未跨过边界的子串权值来表示。那么由于有 \(a\) 个 \(0\)，\(n-a\) 个 \(1\)，我们可以令 \(0\) 的权值为 \(n-a\)，\(1\) 的权值为 \(-a\)，这样就有 \(a(n-a) + (n-a)(-a) = 0\)。
接下来考虑平衡子串的性质。我们先考虑所有长度为 \(l\) 的子串。假设此时这个子串中出现了 \(k\) 个 \(0\)，那么它的权值为 \(k(n-a) - (l-k) a = nk - al\)。
考虑平衡串的限制，\(0\) 的出现次数变化只有 \(1\)。那么我们不妨设两种出现次数为 \(k_l, k_l + 1\)（后面将省去下标）。
此时我们需要先确定 \(k\) 是什么。不妨考虑所有子串中 \(0\) 的出现次数之和。那么对于每一个 \(0\)，它会被 \(l\) 个子串统计到，那么出现次数之和为 \(al\)。我们设其中有 \(p\) 个子串出现了 \((k+1)\) 个 \(0\)，有 \((n-p)\) 个子串出现了 \(k\) 个 \(0\)，那么有 \((n-p)k + p(k+1) = al\)，化简可得 \(nk + p = al\)。由于 \(p\in \lbrack0, n)\)，那么可以得到 \(p = al \bmod n\)，同时有 \(nk-al = -p\)。
如果 \(p = 0\)，那么所有子串的权值都是 \(0\)；如果 \(p \ne 0\)，那么 \(p \in (0, n)\)，而考虑两种子串的权值，有 \(nk-al = -p \in (-n, 0), n(k+1) - al = n - p \in (0, n)\)。综上所述，任意一个子串的权值均 \(\in (-n, n)\)。
我们考虑将子串的权值变成前缀和差分。由于我们上面构造的总和为 \(0\)，那么我们可以发现任意一个子串都可以表示成两个前缀和之差。那么设前缀和为 \(q_i\)，平衡的条件实际上等价于 \(\forall i, j, q_i - q_j \in (-n, n)\)。我们只需要满足极差 \(<n\)，就能满足上述的性质了。
假如我们枚举一个 \(q_i\) 的值域的区间 \(\lbrack x, x+n)\)，发现，我们的操作相当于每次让前缀和 \(+ (n-a)\) 或 \(-a\)。由于区间长度为 \(n-1\)，那么我们每次只能进行两种操作中的一种，那么我们是可以唯一构造出一个 \(01\) 串的。同时，前者我们可以看做是后者再\(\bmod n\)，于是 \(q_i \equiv -ai \pmod n\)。由于 \(\gcd(a, n) = 1\)，根据裴蜀定理，我们可以得知 \(q_i \bmod n\) 经过了 \(\lbrack 0, n)\) 中的所有数恰好一次，即 \(q_i\) 经过了 \(\lbrack x, x+n)\) 中的所有数恰好一次。
此时我们已经可以构造出这个字符串了，直接用 NTT 跑通配符匹配可以做到 \(O(n^2 \log n)\)。
考虑优化。我们发现，上述的区间 \(\lbrack x, x+n)\) 有 \(n\) 种，每一个区间唯一对应着字符串的一种循环移位。那么我们不考虑对每个循环移位进行匹配，而是对每一个 \(\lbrack x, x+n)\) 得到的字符串进行匹配。我们考虑 \(x \to x - 1\) 后有哪些变化。发现，此时只有最大值会到值域区间外，此时上一步操作就不再能执行 \(+ (n - a)\)，而是执行 \(-a\)。而两个操作的差是 \(n\)，所以我们发现原来的最大值就变成现在的最小值了。而对于下一步操作，原来的 \(-a\) 变成了 \(+ (n-a)\)，此时我们又回到了原来的点。那么我们发现，从 \(x \to x-1\) 只会使得字符串改变 \(2\) 个字符。这样的匹配是容易维护的，我们只需要维护当前有多少位匹配上了即可，这样就可以 \(O(n^2)\) 进行匹配了。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 17005;
int T, n, m;
char s[MAXN], t[MAXN], S[MAXN];
int loc[MAXN];
int main() {
freopen("bal.in", "r", stdin);
freopen("bal.out", "w", stdout);
scanf("%d", &T);
while (T--) {
scanf("%s", s + 1);
m = strlen(s + 1);
int ans = 0;
for (int A = 0; A <= m; A++) {
int g = __gcd(A, m);
int n = m / g, a = A / g;
bool flag = true;
for (int i = 1; i <= n; i++) {
S[i] = '?';
for (int j = 0; j < g; j++) {
if (s[i + j * n] == '0') {
if (S[i] == '1') {
flag = false;
break;
} else {
S[i] = '0';
}
}
if (s[i + j * n] == '1') {
if (S[i] == '0') {
flag = false;
break;
} else {
S[i] = '1';
}
}
}
if (!flag) break;
}
if (!flag) continue;
int pre = 0;
for (int i = 1; i <= n; i++) {
if (pre - a >= 0) {
pre -= a;
t[i] = '1';
} else {
pre += n - a;
t[i] = '0';
}
loc[pre] = i;
}
int tot = 0;
#define match(i) ((t[i] == '0' && S[i] != '1') + (t[i] == '1' && S[i] != '0'))
for (int i = 1; i <= n; i++) {
tot += match(i);
}
ans += tot == n;
for (int i = n - 1; i >= 1; i--) {
int p = loc[i];
tot -= match(p) + match(p + 1);
t[p] = '1';
t[p + 1] = '0';
tot += match(p) + match(p + 1);
ans += tot == n;
}
printf("\n");
}
printf("%d\n", ans);
}
return 0;
}