C. Complementary XOR
给定两个长度均为 \(n\) 的 \(\tt{01}\) 串 \(a,b\)，你可以使用下面这种操作：
- 选择两个下标 \(l,r(1\le l\le r\le n)\)。
- 对于所有的 \(i\in[l,r]\)，取反 \(a_i\)。
- 对于所有的 \(i\in[1,l)\cup(r,n]\)，取反 \(b_i\)。
判断是否可以通过使用不超过 \(n+5\) 次操作让两个串里的所有元素都变成 \(00\)。如果可以，输出一种可能的方案。
\(n \leq 2 \times 10^5\)。
考虑连续的两次操作 \([l_1,r_1],[l_2,r_2]\)，简单讨论一下可以发现这相当于将 \(a,b\) 中这两个区间分别取反。
由此可得，如果执行了偶数次操作后 \(a,b\) 均为 \(0\)，那么初始时一定有 \(a=b\)。
类似地，可以得到如果执行了奇数次操作后 \(a,b\) 均为 \(0\)，那么初始时 \(a,b\) 的每一位一定都不同。
然后考虑如何构造：
我们先把所有 \(a_i = 1\) 的位置用一次操作 \([i,i]\) 消掉。
之后根据上面的两种情况，\(b\) 此时可能均为 \(0\) 或均为 \(1\)。如果均为 \(0\) 我们就做完了，否则我们需要用奇数次操作使得 \(a\) 不变。
执行 \([1,1]\)、\([1,2]\)、\([2,2]\) 三次操作就行了。时间复杂度 \(O(n)\)。
code
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n;
void solve() {
cin >> n;
string a, b;
cin >> a >> b;
bool same = true, diff = true;
for (int i = 0; i < n; i++) {
if (a[i] == b[i]) {
diff = false;
} else {
same = false;
}
}
if (!same && !diff) {
cout << "NO" << "\n";
return;
}
int one = 0;
for (int i = 0; i < n; i++)
if (a[i] == '1') one++;
if (one % 2 == diff) {
cout << "YES" << "\n";
cout << one << "\n";
for (int i = 0; i < n; i++)
if (a[i] == '1')
cout << i + 1 << " " << i + 1 << "\n";
} else {
cout << "YES" << "\n";
cout << one + 3 << "\n";
cout << 1 << " " << 1 << "\n";
cout << 2 << " " << 2 << "\n";
cout << 1 << " " << 2 << "\n";
for (int i = 0; i < n; i++)
if (a[i] == '1')
cout << i + 1 << " " << i + 1 << "\n";
}
}
int main() {
ios :: sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while (t--) solve();
return 0;
}
D. Count GCD
给定 \(n,m\) 和一个数列 \(a\)，求有多少长度为 \(n\) 的序列 \(b\)，使得 \(b_i \in [1,m]\)，且 \(\gcd \limits_{j=1}^i b_j = a_i\)。
答案对 \(998244353\) 取模。
\(n \leq 2 \times 10^5\)，\(m \leq 10^9\)。
显然，如果 \(a_{i} \nmid a_{i-1}\) 那么无解。
容易发现每个位置是独立的，对每个位置分别求出 \(1 \leq x \leq m\) 且 \(\gcd(a_{i-1},x) = a_i\) 的解数即可。
不妨设 \(a_{i} \times p = a_{i-1}\)，则 \(\gcd(a_i \times p, x) = a_i\)，即 \(\gcd(p, \frac{x}{a_i}) = 1\)。
记 \(q = \frac{x}{a_i}\)，要求的就是 \(1 \leq q \leq \lfloor \frac{m}{a_i} \rfloor\) 且 \(\gcd(p,q) = 1\) 的 \(q\) 的个数，容斥即可。
时间复杂度 \(O(n \sqrt m)\)。
code
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5, mod = 998244353;
#define pb emplace_back
int n, m, a[N];
int calc(int x, int lim) {
vector <int> p;
int rb = __builtin_sqrt(x);
for (int i = 2; i <= rb; i++) {
if (x % i)
continue;
p.pb(i);
while (x % i == 0)
x /= i;
}
if (x > 1)
p.pb(x);
int v = p.size();
int ans = 0;
for (int S = 0; S < (1 << v); S++) {
int cur = 1;
for (int i = 0; i < v; i++)
if (S & (1 << i))
cur *= p[i];
if (__builtin_popcount(S) & 1) {
ans -= (lim / cur);
} else {
ans += (lim / cur);
}
}
return ans;
}
void solve() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
int ans = 1;
for (int i = 2; i <= n; i++) {
if (a[i - 1] % a[i]) {
cout << 0 << "\n";
return;
}
int x = a[i - 1] / a[i];
int lim = m / a[i];
ans = 1ll * ans * calc(x, lim) % mod;
}
cout << ans << endl;
}
int main() {
ios :: sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while (t--) solve();
return 0;
}
E. Bracket Cost
给定一个长度为 \(n\) 的括号序列。你可以做以下操作：
- 选择一个子串，将其循环右移一位。
- 在括号序列的任意位置加一个左括号或右括号。
定义一个括号序列的代价为能将其变为匹配序列的最少操作次数，求这个括号序列所有的子串的代价之和。
\(n \leq 2 \times 10^5\)。
先无脑前缀和一下，考虑如何形式化地表示一个子串的代价。
对于一个括号序列，设 \(x,y\) 分别为失配的左、右括号数量，则最少操作次数为 \(\max(x,y)\)。这是因为删掉匹配的括号后，失配的括号形如 ))))((((，进行 \(\min(x,y)\) 次右移再补上 \(|x-y|\) 个括号即可。
记前缀和为 \(s\)。对于子串 \([l,r]\)，找到 \(s_x = \min \limits_{i = l-1}^r \{ s_i \}\)，那么前缀会有 \(-(s_x - s_{l-1})\) 个 ) 失配，后缀会有 \(s_r-s_x\) 个 ( 失配。因此答案即为：
考虑 \(s_i\) 的贡献，第一项容易计算，第二项单调栈即可。时间复杂度 \(O(n \log n)\)。
code
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
typedef long long LL;
int n, a[N];
int stk[N], tp, le[N], ri[N];
LL ans;
void solve() {
string s;
cin >> n >> s;
for (int i = 1; i <= n; i++) {
if (s[i - 1] == '(') {
a[i] = a[i - 1] + 1;
} else {
a[i] = a[i - 1] - 1;
}
}
tp = 0;
for (int i = 0; i <= n; i++) {
while (tp && a[i] < a[stk[tp]])
tp--;
if (tp == 0) {
le[i] = 0;
} else {
le[i] = stk[tp] + 1;
}
stk[++tp] = i;
}
tp = 0;
for (int i = n; i >= 0; i--) {
while (tp && a[i] <= a[stk[tp]])
tp--;
if (tp == 0) {
ri[i] = n;
} else {
ri[i] = stk[tp] - 1;
}
stk[++tp] = i;
}
ans = 0;
for (int i = 0; i <= n; i++) {
ans -= 1ll * (i - le[i] + 1) * (ri[i] - i + 1) * a[i];
ans += a[i];
}
sort(a, a + n + 1);
for (int i = 0; i <= n; i++)
ans += 1ll * a[i] * i;
cout << ans << "\n";
}
int main() {
ios :: sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while (t--) solve();
return 0;
}
F. Majority
定义一个 \(01\) 串 \(s\) 是好的，当且仅当 \(s\) 可以通过若干次以下操作变为全 \(1\) 串：
-
选择一个区间 \([i,j]\) 满足 \(s_i=s_j=1\)，\(2 \sum \limits_{k=i}^j s_k\ge j-i+1\)。
-
将 \(k\in[i,j]\) 的 \(s_k\) 全部改为 \(1\)。
给定 \(n\) 和 \(p\)，求有多少个长度为 \(n\) 的 \(01\) 串是好的，答案对 \(p\) 取模。
显然，一个 \(01\) 串合法的必要条件是 \(s_1 = s_n = 1\)，我们不妨直接钦定这两个位置为 \(1\)。
考虑容斥，为此我们需要建立合法串和不合法串之间的联系。一个套路的做法是找到不合法串 “无法操作” 的终态并分析其结构，然后将所有不合法状态映射到这些状态上。
在本题中，“无法操作” 的状态 \(s\) 是这样的：
\(s\) 可以被划分为 \(2p+1\) 段，奇数段全为 \(1\)，偶数段全为 \(0\)。并且每个偶数段的长度大于与其相邻的两个奇数段长度之和。
接下来考虑如何将不合法状态映射到一个终态。对于一个终态 \(s\) 而言，一个不合法状态 \(s'\) 能够对应到它当且仅当对于 \(s\) 的奇数段，\(s'\) 的那些段都能变为全 \(1\) 串。也就是说，我们要考虑的其实是原问题的一个子问题。
那么计数就很简单了。我们设 \(f,g\) 分别为合法串和不合法串的答案，先通过子问题的 \(f'\) 算出当前问题的 \(g\)，然后根据容斥关系就能够算出当前问题的 \(f\) 了。
具体来说，设 \(f_i\) 表示长为 \(i\) 的合法段的数量，\(g_{i,j}\) 表示当前的 \(2p+1\) 段长度和为 \(i\)，最后一段长度为 \(j\) 的方案数。根据容斥关系，我们有：\(f_i + \sum \limits_{j=1}^{i-1} g_{i,j} = 2^{n-2}\)。
然后考虑如何递推出 \(g\)，根据定义，我们枚举倒数第二段和倒数第三段的长度，则有：
\[g_{i,j} = f_j \sum_{x=1}^i \sum_{k=1}^{\min(i-x,x-j-1)} g_{i-j-x,k} \]由于定义域外的值一定都是 \(0\)，那么原式相当于 \(g_{i,j} = f_j \sum \limits_x \sum \limits_k [j + k < x] g_{i-j-x,k}\)。
令 \(p = i - j - x\)，那么条件即为 \(p+k \leq i - 2j - 1\)，即 \(g_{i,j} = f_j \sum \limits_{p+k \leq i - 2j - 1} g_{p,k}\)。
容易利用前缀和优化至 \(O(n^2)\)，然后就做完了。
code
#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 5;
int n, mod, f[N], g[N][N], s[N], h[N][N];
int main() {
ios :: sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> mod;
f[1] = s[1] = 1;
int p = 1;
for (int i = 2; i <= n; i++) {
f[i] = p;
for (int j = 1; j <= i; j++) {
if (i - 2 * j - 2 >= 1) {
g[i][j] = 1ll * f[j] * s[i - 2 * j - 2] % mod;
}
f[i] = (f[i] + mod - g[i][j]) % mod;
}
g[i][i] = f[i];
for (int j = 1; j <= i; j++) {
h[i][j] = (h[i - 1][j + 1] + g[i][j]) % mod;
}
s[i] = (s[i - 1] + h[i][1]) % mod;
p = 1ll * p * 2 % mod;
}
cout << f[n] << "\n";
return 0;
}
G. Doping
定义排列 \(a\) 的权值 \(f(a)\) 为 \(a\) 最少可以划分成多少个区间，使得每个区间都是公差为 \(1\) 的等差数列。
给定长度为 \(n\) 的排列 \(p\)，对于 \(k=1,2,\cdots,n\) 求出，有多少个长度为 \(n\) 的排列 \(p'\)，满足 \(p'\) 字典序比 \(p\) 小，且 \(f(p')=k\)，答案对 \(P\) 取模。
\(n \leq 2 \times 10^3\)。
考虑容斥，设 \(f_i\) 表示恰好能被分为 \(i\) 段的排列数量，\(g_i\) 表示钦定分为 \(i\) 段，但不要求相邻两端接口处的差 \(>1\) 的排列数量。那么有：\(g_i = \sum \limits_{j=1}^i \dbinom{n-j}{j-i} f_i\)。
其意义为恰好被分成 \(j\) 个段的排列还有 \(n-j\) 个位置可以切开，需要从中选择 \(i-j\) 个位置。
要求字典序小于 \(p\)，考虑枚举 LCP 之后计算。假设我们现在确定了一个长为 \(i-1\) 的 LCP，第 \(i\) 位需要填一个小于 \(p_i\) 的数。考虑将 \(p_{i\dots n}\) 分为 \(<p_i\) 和 \(\ge p_i\) 两类，设两类数中分别有 \(a_1,a_2\) 个差为 \(1\) 的数对，同时在值域上分别形成了 \(b_1,b_2\) 个连续段。
枚举 \(p'_{i\dots n}\) 被分成了 \(k\) 段 (\(b_1+b_2 \leq k \leq b_1+b_2+a_1+a_2\))，那么方案数为：
\[\sum_{j=0}^k \frac{b_1 + j}{k} k! \binom{a_1}{j} \binom{a_2}{k - b_1 - b_2 - j} \]简单解释一下含义：我们枚举小于 \(p_i\) 的数多构成了多少个连续段，那么后面不小于 \(p_i\) 的数多构成的连续段数也随之确定了。由于要求 \(p'_i < p_i\)，因此在所有 \(k!\) 种连续段的排列方式中恰有 \(\dfrac{b_1 + j}{k}\) 是合法的。
利用 \(m \dbinom{n}{m} = n \dbinom{n-1}{m-1}\) 和范德蒙德卷积可以得到上式等于
\[b_1(k-1)!\binom{a_1+a_2}{k-b_1-b_2} + a_1(k-1)! \binom{a_1 + a_2 - 1}{k-b_1 - b_2 - 1} \]当然还有特殊情况，即 \(p_i = p_{i-1}+1\)，此时可以选择不钦定 \(i\) 作为一段的起点，这样的方案数为 \(\dfrac{k!}{k}\dbinom{a_1+a_2}{k-b_1-b_2}\)。这是因为在这种情况下 \(p_{i-1}+1\) 一定是一个连续段的起点，可以不枚举。而补满缺少的 \(k-b_1-b_2\) 个钦定的连续段之后的所有连续段排列有 $\dfrac{1}{k} $ 满足条件。
但如果对每个 \(i\) 都进行容斥复杂度就会达到 \(O(n^3)\)，我们希望只在最后进行一次容斥。考虑 DP，设 \(g_{i,j}\) 表示只考虑 \(p_{i\dots n}\) 时 \(g_j\) 的值。转移比较简单，如果 \(p_i-1=p_{i-1}\) 就可以选择是否钦定分段，那么有 \(g_{i,j}=g_{i,j-1}+g_{i,j}\)。否则一定要分段，即 \(g_{i,j}=g_{i,j-1}\)。
只需要在 \(g_{i,j}\) 处加入 \(p_{i\dots n}\) 钦定被分为 \(j\) 段的方案数，然后往前推即可。时间复杂度 \(O(n^2)\)。
code
#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 5;
int n, mod, a[N], f[N], g[N];
int fac[N], C[N][N];
bool vis[N];
int main() {
ios :: sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> mod;
for (int i = 1; i <= n; i++)
cin >> a[i];
C[0][0] = 1;
for (int i = 1; i <= n; i++) {
C[i][0] = 1;
for (int j = 1; j <= i; j++) {
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
}
}
fac[0] = 1;
for (int i = 1; i <= n; i++) {
fac[i] = 1ll * fac[i - 1] * i % mod;
}
for (int i = n; i >= 1; i--) {
if (i > 1 && a[i - 1] == a[i] - 1) {
for (int j = n - 1; j >= 0; j--)
f[j + 1] = (f[j + 1] + f[j]) % mod;
} else {
for (int j = n - 1; j >= 0; j--)
f[j + 1] = f[j];
f[0] = 0;
}
vis[a[i]] = true;
int a1 = 0, b1 = 0;
int a2 = 0, b2 = 0;
for (int j = 1; j < a[i]; j++) {
if (!vis[j])
continue;
if (vis[j - 1]) {
b1++;
} else {
a1++;
}
}
for (int j = a[i]; j <= n; j++) {
if (!vis[j])
continue;
if (vis[j - 1]) {
b2++;
} else {
a2++;
}
}
int A = a1 + a2;
int B = b1 + b2;
for (int j = A; j <= A + B; j++) {
f[j] = (f[j] + 1ll * fac[j - 1] * a1 % mod * C[B][j - A] % mod) % mod;
if (j > A) {
f[j] = (f[j] + 1ll * fac[j - 1] * b1 % mod * C[B - 1][j - A - 1] % mod) % mod;
}
if (i > 1 && vis[a[i - 1] + 1] && a[i - 1] + 1 < a[i]) {
f[j - 1] = (f[j - 1] + 1ll * fac[j - 1] * C[B][j - A] % mod) % mod;
}
}
}
for (int i = 1; i <= n; i++) {
g[i] = f[i];
for (int j = 1; j < i; j++) {
g[i] = (g[i] + mod - 1ll * g[j] * C[n - j][i - j] % mod) % mod;
}
}
for (int i = 1; i <= n; i++)
cout << g[i] << " ";
cout << "\n";
return 0;
}
H. BinaryStringForces
NOIp 后再补吧