Atcoder Grand Contest 35

Problem C. Skolem XOR Tree

$N$ 为 $2$ 的次幂时无解，因为不可能有路径在那一位上异或和为 $1$ ，以下算法对于剩余情况均给出了一组构造。

对于一个异或和为 $0$ 的点集，我们可以将其仿照样例的解排成一排，即可满足这些点的限制。

注意到对于 $4$ 的倍数 $N$ ，有 $N\oplus (N+1)\oplus (N+2)\oplus (N+3)=0$ 。

因此，记 $1,2,\dots ,N$ 的异或和为 $S(N)$ ，有
$$S(N)=\{\begin{array}{rcl}N& & N\equiv 0(mod4)\\ 1& & N\equiv 1(mod4)\\ N+1& & N\equiv 2(mod4)\\ 0& & N\equiv 3(mod4)\end{array}$$

因此，对于 $N\equiv 3(mod4)$ 的情况，可以直接仿照样例。

对于 $N\equiv 1(mod4)$ 的情况，可以直接仿照样例排列 $2,3,\dots ,N$ ，再将 $1,N+1$ 分别接在 $2,3$ 两侧即可。

对于 $N\equiv 0(mod4)$ 的情况，可以直接仿照样例排列 $1,2,\dots ,N-1$ ，我们需要使得异或和为 $N$ 的两个数相邻，令 $N$ 的最高位为 $X$ ，可以交换 $X-1,X\oplus N$ ，使得 $X\oplus N,X$ 排在相邻的位置。

对于 $N\equiv 2(mod4)$ 的情况，可以直接仿照样例排列 $2,3,\dots ,N-1$ ，我们需要使得异或和为 $1,N$ 的两个数相邻，令 $N$ 的最高位为 $X$ ，可以交换 $X-1,X\oplus N$ ，使得 $X\oplus N,X$ 排在相邻的位置，若交换涉及到 $2,3$ ，则把另一个也对应地交换过去即可。

时间复杂度 $O(N)$ 。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int a[MAXN];
int main() {
	int n, power = 1; read(n);
	while (power < n) power <<= 1;
	if (n == power) {
		puts("No");
		return 0;
	}
	puts("Yes");
	power >>= 1;
	if (n % 4 == 0) {
		for (int i = 1; i <= n - 1; i++)
			a[i] = i;
		swap(a[power - 1], a[n ^ power]);
		for (int i = 1; i <= n - 2; i++)
			printf("%d %dn", a[i], a[i + 1]);
		printf("%d %dn", a[n - 1], n + a[1]);
		for (int i = 1; i <= n - 2; i++)
			printf("%d %dn", n + a[i], n + a[i + 1]);
		printf("%d %dn", n, power);
		printf("%d %dn", 2 * n, n ^ power);
	}
	if (n % 4 == 1) {
		for (int i = 2; i <= n - 1; i++)
			printf("%d %dn", i, i + 1);
		printf("%d %dn", n, n + 2);
		for (int i = 2; i <= n - 1; i++)
			printf("%d %dn", n + i, n + i + 1);
		printf("%d %dn", 1, 2);
		printf("%d %dn", n + 1, 3);
	}
	if (n % 4 == 2) {
		for (int i = 2; i <= n - 1; i++)
			a[i] = i;
		swap(a[power - 1], a[n ^ power]);
		if ((n ^ power) == 2 && n != 6) swap(a[power - 2], a[3]);
		for (int i = 2; i <= n - 2; i++)
			printf("%d %dn", a[i], a[i + 1]);
		printf("%d %dn", a[n - 1], n + a[2]);
		for (int i = 2; i <= n - 2; i++)
			printf("%d %dn", n + a[i], n + a[i + 1]);
		printf("%d %dn", n, power);
		printf("%d %dn", 2 * n, n ^ power);
		printf("%d %dn", 1, 2);
		printf("%d %dn", 1 + n, 3);
	}
	if (n % 4 == 3) {
		for (int i = 1; i <= 2 * n - 1; i++)
			printf("%d %dn", i, i + 1);
	}
	return 0;
}

Problem D. Add and Remove

考虑时间倒流，找到最后一次被操作的位置 $x$ ，则 $x$ 上当时的数字会被计算 $2$ 倍的贡献，此后，问题可以递归至两侧解决。

我们需要在状态中计录 $(l,r,cl,cr)$ ，表示考虑区间 $[l,r]$ 内的操作， $l-1$ 处的数字会被计算 $cl$ 倍的贡献， $r+1$ 处的数字会被计算 $cr$ 倍的贡献。

记 $dp(l,r,cl,cr)$ 为该状态下的最优解，则有
d p ( l , r , c l , c r ) = min ⁡ i = l r { ( c l + c r ) a i + d p ( l , i − 1 , c l , c l + c r ) + d p ( i + 1 , r , c l + c r , c r ) } dp(l,r,cl,cr)=min_{i=l}^{r}{(cl+cr)a_i+dp(l,i-1,cl,cl+cr)+dp(i+1,r,cl+cr,cr)} dp(l,r,cl,cr)=i=lminr​{(cl+cr)ai​+dp(l,i−1,cl,cl+cr)+dp(i+1,r,cl+cr,cr)}

考虑该 $dp$ 的状态数， $l,r$ 显然有 $O(N^2)$ 组，可以发现 $cl,cr$ 的取值与上述转移式中的 $i$ 无关，因此每一层转移至多增加一倍，是 $O(2^N)$ 级别的。

时间复杂度 $O(2^N{N}^3)$ ，其中 $N=16$ ，常数较小。

以下代码通过 $std::map$ 实现。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 55;
const long long INF = 1e18;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int n, a[MAXN], Max;
map <pair <int, int>, ll> dp[MAXN][MAXN];
ll work(int l, int r, int cl, int cr) {
	if (l > r) return 0;
	if (dp[l][r].count(make_pair(cl, cr)))
		return dp[l][r][make_pair(cl, cr)];
	ll ans = INF; for (int i = l; i <= r; i++)
		chkmin(ans, 1ll * a[i] * (cl + cr) + work(l, i - 1, cl, cl + cr) + work(i + 1, r, cl + cr, cr));
	return dp[l][r][make_pair(cl, cr)] = ans;
}
int main() {
	read(n);
	for (int i = 1; i <= n; i++)
		read(a[i]);
	writeln(a[1] + a[n] + work(2, n - 1, 1, 1));
	return 0;
}

Problem E. Develop

考虑构建一张这样的图： $i$ 向 $i-2,i+K$ 连有向边。

考虑选定一个点集 $S$ 删除，判断其是否可行。

若选定的点在上述的图中存在环，那么显然不可能全部删除，若不存在环，那么可以直接按照拓补序进行操作，全部删除。

因此，我们需要计算不构成环的点集 $S$ 数。

若 $K$ 为偶数，我们显然可以将奇数位和偶数位分开处理，要求即为不同时选定相邻的 $\frac{K}{2}+1$ 个点，可以通过简单的 $O(N^2)$ 动态规划完成。

若 $K$ 为奇数，考虑一个由 $+K,-2$ 组成的环，可以发现， $+K$ 一定恰好出现两次，否则，就可以找到一个更小的环。

考虑使用类似的动态规划，在状态中计入 $(i,j,k,lj,lk)$ ，分别表示处理了前 $i$ 个位置，奇、偶数位当前分别连续选定了 $j,k$ 个位置，奇数位不能连续选到 $lj$ ，偶数位不能连续选到 $lk$ 。

考虑奇数位 $i$ 时的转移，若不选择 $i$ 号位置，则有转移
$$(i-1,j,k,lj,lk)\Rightarrow (i,0,k,N+1,lk)$$

若 $i\ne lj$ ，则可以选择 $i$ 号位置，同时，若 $i-K\ge i-2\ast k+1$ ，也即偶数位的能够通过 $+K$ 到达 $i$ ，就需要更新 $lk$ 的限制，有转移
( i − 1 , j , k , l j , l k ) ⇒ ( i , j + 1 , k , l j , max ⁡ { l k , i − 2 ∗ j + K } ) (i-1,j,k,lj,lk)Rightarrow(i,j+1,k,lj,max{lk,i - 2 * j + K}) (i−1,j,k,lj,lk)⇒(i,j+1,k,lj,max{lk,i−2∗j+K})

否则，即不需要更新 $lk$ 的限制，有转移
$$(i-1,j,k,lj,lk)\Rightarrow (i,j+1,k,lj,lk)$$

偶数位的转移类似。

注意到 $lj,lk$ 中，只有对应的 $j$ 或 $k$ 较大的一个才有意义，因此 $(lj,lk)$ 的个数是 $O(K)$ 级别的，总状态数就是 $O(N^{3}K)$ 级别的了。

时间复杂度 $O(N^{3}K)$ ，常数较小。

以下代码通过 $std::map$ 实现。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 155;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int n, m, P;
void update(int &x, int y) {
	x += y;
	if (x >= P) x -= P;
}
map <pair <int, int>, int> dp[MAXN][MAXN][MAXN];
int main() {
	read(n), read(m), read(P);
	if (m % 2 == 0) {
		static int dp[MAXN][MAXN];
		m /= 2, dp[0][0] = 1;
		for (int i = 1; i <= n; i++)
		for (int j = 0; j <= m; j++) {
			update(dp[i][0], dp[i - 1][j]);
			if (j != m) update(dp[i][j + 1], dp[i - 1][j]);
		}
		int ans = 0, bns = 0;
		for (int i = 0; i <= m; i++) {
			update(ans, dp[n / 2][i]);
			update(bns, dp[(n + 1) / 2][i]);
		}
		writeln(1ll * ans * bns % P);
	} else {
		dp[0][0][0][make_pair(n + 1, n + 1)] = 1;
		for (int i = 1; i <= n; i++)
		for (int j = 0; j <= n; j++)
		for (int k = 0; k <= n; k++) {
			if (i & 1) {
				for (auto x : dp[i - 1][j][k]) {
					pair <int, int> tmp = x.first; tmp.first = n + 1;
					update(dp[i][0][k][tmp], x.second);
					if (i != x.first.first) {
						tmp = x.first;
						if (i - m >= i - 2 * k + 1) chkmin(tmp.second, i - 2 * j + m);
						if (tmp.second >= i) update(dp[i][j + 1][k][tmp], x.second);
					}
				}
			} else {
				for (auto x : dp[i - 1][j][k]) {
					pair <int, int> tmp = x.first; tmp.second = n + 1;
					update(dp[i][j][0][tmp], x.second);
					if (i != x.first.second) {
						tmp = x.first;
						if (i - m >= i - 2 * j + 1) chkmin(tmp.first, i - 2 * k + m);
						if (tmp.first >= i) update(dp[i][j][k + 1][tmp], x.second);
					}
				}
			}
		}
		int ans = 0;
		for (int i = 0; i <= n; i++)
		for (int j = 0; j <= n; j++) {
			for (auto x : dp[n][i][j])
				update(ans, x.second);
		}
		writeln(ans);
	}
	return 0;
}

Problem F. Two Histograms

对于一对数 $(i,j)$ ，若 $k_i+1=j,l_j=i$ ，我们可以令 $k_i$ 加 $1$ ， $l_j$ 减 $1$ ，得到的结果作用在网格上显然会得到相同的网格。

经过有限次上述操作，我们可以得到一个不能继续上述操作的数列，我们称这样的数列是标准的，以下证明标准的数列与可以到达的网格一一对应。

一个数列自然只会生成一个网格，因此我们只需要证明不同的标准数列生成的网格不同即可。

证明：
假设两个数列 $(l,k),(l^{\prime },k^{\prime })$ 不同，且生成了相同的网格。
令 $j$ 为最小的满足 $l_j\ne l_j^{\prime }$ 的位置，且不失一般性地令 $l_j<l_j^{\prime }$ 。
若 $j=1$ ，考虑数列 $(l^{\prime },k^{\prime })$ ， $A_{l_j^{\prime },j}\ge 1$ ，而 $l_j<l_j^{\prime }$ ，因此 $A_{l_j^{\prime },j}\le 1$ ，从而 $A_{l_j^{\prime },j}=1,k_{l_j^{\prime }}^{\prime }=0$ ，可以发现， 数列 $(l^{\prime },k^{\prime })$ 不是一个标准的数列，矛盾。
若 $j>1$ ，同 $j=1$ 的情况，可以发现， $A_{j,l_j^{\prime }}=1$ ，因此 $k_{l_j^{\prime }}\ge j,k_{l_j^{\prime }}^{\prime }<j$ ，又因为数列 $(l^{\prime },k^{\prime })$ 是一个标准的数列， $k_{l_j^{\prime }}^{\prime }\ne j-1$ ，并且 $l_{j-1}=l_{j-1}^{\prime }$ ，因此数列 $(l,k)$ 生成的网格在 $A_{j-1,l_j^{\prime }}$ 处大于数列 $(l^{\prime },k^{\prime })$ 生成的网格在 $A_{j-1,l_j^{\prime }}$ 处的值，矛盾。

那么，我们只需要对标准的数列计数即可，由容斥原理，显然有
A n s = ∑ i = 0 min ⁡ { N , M } ( − 1 ) i × ( N i ) × ( M i ) × i ! × ( N + 1 ) M − i × ( M + 1 ) N − i Ans=sum_{i=0}^{min{N,M}}(-1)^itimesbinom{N}{i}timesbinom{M}{i}times i!times(N+1)^{M-i}times(M+1)^{N-i} Ans=i=0∑min{N,M}​(−1)i×(iN​)×(iM​)×i!×(N+1)M−i×(M+1)N−i

时间复杂度 $O(N)$ 或 $O(NLogV)$ 。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 5;
const int P = 998244353;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int fac[MAXN], inv[MAXN];
int power(int x, int y) {
	if (y == 0) return 1;
	int tmp = power(x, y / 2);
	if (y % 2 == 0) return 1ll * tmp * tmp % P;
	else return 1ll * tmp * tmp % P * x % P;
}
int binom(int x, int y) {
	if (y > x) return 0;
	else return 1ll * fac[x] * inv[y] % P * inv[x - y] % P;
}
void init(int n) {
	fac[0] = 1;
	for (int i = 1; i <= n; i++)
		fac[i] = 1ll * fac[i - 1] * i % P;
	inv[n] = power(fac[n], P - 2);
	for (int i = n - 1; i >= 0; i--)
		inv[i] = inv[i + 1] * (i + 1ll) % P;
}
void update(int &x, int y) {
	x += y;
	if (x >= P) x -= P;
}
int main() {
	int n, m; read(n), read(m);
	init(max(n, m));
	int ans = 0;
	for (int i = 0; i <= min(n, m); i++)
		if (i & 1) update(ans, P - 1ll * binom(n, i) * binom(m, i) % P * fac[i] % P * power(n + 1, m - i) % P * power(m + 1, n - i) % P);
		else update(ans, 1ll * binom(n, i) * binom(m, i) % P * fac[i] % P * power(n + 1, m - i) % P * power(m + 1, n - i) % P);
	writeln(ans);
	return 0;
}

Atcoder Grand Contest 36

Problem D. Negative Cycle

考虑 $0$ 号节点到每个节点 $i$ 的最短路 $di{s}_i$ ，由于本来存在的边， $di{s}_i$ 是递减的，且相邻的位置相差至多为 $1$ 。

考虑一个确定的最短路序列 $di{s}_i$ ，我们需要删掉一些边以确保其不能被更新，所花费的代价即为 $di{s}_i$ 对应的代价。

计算代价的过程是直观的，考虑相邻的两段 $di{s}_i$ 相同的区间 $[a,b],[b+1,c]$ ，其中 $[b+1,c]$ 中连出的边需要删掉连向 $[b+2,c]$ 的向前的边，以及连向 $[0,a-1]$ 的向后的边。

不难发现在状态中计入 $a,b$ ，转移时枚举 $c$ ，利用部分和优化即可得到一个 $O(N^3)$ 的动态规划解法。

时间复杂度 $O(N^3)$ 。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 505;
const long long INF = 1e18;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int n, a[MAXN][MAXN];
ll s[MAXN][MAXN], cost[MAXN][MAXN], dp[MAXN][MAXN];
int main() {
	read(n);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j < i; j++)
			read(a[i][j]);
		for (int j = i + 1; j <= n; j++)
			read(a[i][j]);
	}
	for (int i = 1; i <= n; i++)
	for (int j = 1; j <= n; j++)
		s[i][j] = s[i][j - 1] + a[i][j];
	for (int i = 0; i <= n; i++)
	for (int j = i + 1; j <= n; j++)
		dp[i][j] = INF;
	for (int i = 1; i <= n; i++)
	for (int j = i; j <= n; j++) {
		ll res = 0;
		for (int k = i; k <= j; k++)
			res += s[k][j] - s[k][k];
		cost[i][j] = res;
	}
	for (int i = 1; i <= n; i++)
		dp[0][i] = cost[1][i];
	for (int i = 0; i <= n - 1; i++)
	for (int j = i + 1; j <= n; j++) {
		ll tmp = dp[i][j];
		for (int k = j + 1; k <= n; k++) {
			tmp += s[k][i];
			chkmin(dp[j][k], tmp + cost[j + 1][k]);
		}
	}
	ll ans = INF;
	for (int i = 0; i <= n - 1; i++)
		chkmin(ans, dp[i][n]);
	writeln(ans);
	return 0;
}

Problem E. ABC String

不难发现应该将连续的字符当成一个看待，记此时 $A$ 的个数为 $a$ ， $B$ 的个数为 $b$ ， $C$ 的个数为 $c$ ，不失一般性地设 $a\le b\le c$。

考虑选定一个 $A$ 的集合，删除其余的 $A$ ，并将相同的字符重新并起来，由于删除一个 $A$ 至多使得 $b,c$ 减少 $1$ ，因此依然有 $a\le b,a\le c$ 。

仍然设 $a\le b\le c$ ，考虑删除一些 $B,C$ ，使得字符串满足条件。

若 $b=c$ ，我们可以不断地删除不会使得字符串中出现 $AA$ 的 $BC$ 或 $CB$ 。

否则，即 $b<c$ ，记总共 $a+1$ 段字符中包含 $B$ 的段数为 $x$ ，中间的 $a-1$ 段字符中仅由一个 $C$ 组成的段数为 $y$ 。

若 $x<y$ ，显然是无法通过删除一些 $B,C$ 使得 $b=c$ 的，否则，就说明包含 $B$ 的段数不少于仅由一个 $C$ 组成的段数，可以不断地删除不会使得字符串中出现连续相同字符的 $C$ ，使得 $b=c$ 。

因此，我们需要在原串中选出尽量多的 $A$ ，满足得到的字符串中 $x\ge y$ 。

考虑先选取所有的 $A$ ，若 $x\ge y$ ，则找到的一定是最优解，否则记 $d=y-x$ ，删去 $d$ 个与单独的 $C$ 相邻的 $A$ 即可。

时间复杂度 $O(|S|)$ 。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
char s[MAXN]; int n;
vector <pair <int, int>> mod;
void modify(char *s, int n, int x, int y) {
	for (int i = 1; i <= n; i++)
		if (s[i] == x + 'A') s[i] = y + 'A';
		else if (s[i] == y + 'A') s[i] = x + 'A';
}
void init() {
	scanf("%s", s + 1);
	int m = strlen(s + 1);
	int cnt[3] = {0, 0, 0};
	for (int i = 1; i <= m; i++)
		if (s[n] != s[i]) {
			s[++n] = s[i];
			cnt[s[i] - 'A']++;
		}
	s[n + 1] = 0;
	if (cnt[0] > cnt[1]) swap(cnt[0], cnt[1]), modify(s, n, 0, 1), mod.emplace_back(0, 1);
	if (cnt[1] > cnt[2]) swap(cnt[1], cnt[2]), modify(s, n, 1, 2), mod.emplace_back(1, 2);
	if (cnt[0] > cnt[1]) swap(cnt[0], cnt[1]), modify(s, n, 0, 1), mod.emplace_back(0, 1);
	if (cnt[0] == 0) puts(""), exit(0);
}
void sela() {
	int b = 0, c = 0;
	static int pos[MAXN]; int cnt = 0;
	for (int i = 1; i <= n; i++)
		if (s[i] == 'A') pos[++cnt] = i;
	for (int i = 1; i <= cnt; i++) {
		bool occur = false;
		for (int j = pos[i - 1] + 1; j <= pos[i] - 1; j++)
			occur |= s[j] == 'B';
		b += occur;
	}
		bool occur = false;
		for (int j = pos[cnt] + 1; j <= n; j++)
			occur |= s[j] == 'B';
		b += occur;
	for (int i = 1; i <= cnt - 1; i++)
		c += pos[i] == pos[i + 1] - 2 && s[pos[i] + 1] == 'C';
	if (b >= c) return;
	int lft = c - b, tmp = n; n = 0;
	for (int i = 1; i <= tmp; i++)
		if (s[i] == 'A') {
			if (lft != 0 && n >= 2 && s[n] == 'C' && s[n - 1] == 'A') lft--;
			else s[++n] = s[i];
		} else if (s[n] != s[i]) s[++n] = s[i];
	assert(lft == 0);
}
void delc() {
	int delta = 0;
	for (int i = 1; i <= n; i++)
		if (s[i] == 'C') delta++;
		else if (s[i] == 'B') delta--;
	assert(delta >= 0);
	int tmp = n; n = 0; s[tmp + 1] = 0;
	for (int i = 1; i <= tmp; i++)
		if (s[i] == 'C') {
			if (delta != 0 && ((n >= 1 && s[n] != s[i + 1]) || n == 0)) delta--;
			else s[++n] = s[i];
		} else s[++n] = s[i];
	assert(delta == 0);
}
void delb() {
	int a = 0, b = 0, c = 0;
	for (int i = 1; i <= n; i++)
		if (s[i] == 'C') c++;
		else if (s[i] == 'B') b++;
		else a++;
	assert(b == c && b >= a);
	int tmp = n; n = 0; s[tmp + 1] = -1;
	for (int i = 1; i <= tmp; i++)
		if (s[i] == 'A') s[++n] = s[i];
		else if (b > a && n >= 1 && s[n] != 'A' && s[i] != s[n] && s[i + 1] != s[n - 1]) n--, b--, c--;
		else s[++n] = s[i];
	s[n + 1] = 0;
}
int main() {
	init();
	sela();
	delc();
	delb();
	while (!mod.empty()) {
		modify(s, n, mod.back().first, mod.back().second);
		mod.pop_back();
	}
	printf("%sn", s + 1);
	return 0;
}

Problem F. Square Constraints

考虑没有下界的情况，显然每一个点可以匹配的位置是一个前缀，记这些前缀的长度分别为 $a_0,a_1,a_2,\dots (a_0\le a_1\le a_2\le \dots )$ ，那么方案数即为 ${\prod }_i(a_i-i)$ 。

记 $f(i)$ 表示平方和 $\le (2N{)}^2$ 可以匹配的前缀长度， $g(i)$ 表示平方和 $<N^2$ 可以匹配的前缀长度，若 $i\ge N$ 则为 $0$ 。

考虑对下界进行容斥，一个直观地想法是选择 $i$ 个位置取 $g(i)$ ，其余位置取 $f(i)$ ，排序后计算匹配数，乘上 $(-1{)}^i$ 计入答案。

一点关键的观察是如果将不是 $0$ 的 $f(i),g(i)$ ，共 $3N$ 个数排序，所有 $\le N-1$ 的 $i$ 对应的 $f(i)$ 会排在最后 $N$ 个位置，这是因为这些数 $\ge N$ ，而其余数 $\le N$ 。

据此，枚举上面选取的位置数 $i$ ，我们可以直观地用一个 $O(N^2)$ 的动态规划加速上面的枚举，即记 $d{p}_{j,k}$ 表示考虑了排在前面的 $j$ 个位置，选择了 $k$ 个 $g(i)$ 的方案数，转移时将对应的 $f(i),g(i)$ 一同考虑即可。

时间复杂度 $O(N^3)$ 。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 255;
const int MAXM = 505;
const int INF  = 1e9;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int n, m, Q, P;
int dp[MAXM][MAXN];
pair <int, int> a[MAXM];
void update(int &x, int y) {
	x += y;
	if (x >= P) x -= P;
}
int main() {
	read(n), read(Q), P = INF / Q * Q;
	int p = 2 * n - 1, q = 2 * n - 1;
	for (int i = 0; i <= 2 * n - 1; i++) {
		while (i * i + p * p > (2 * n) * (2 * n) && p >= 0) p--;
		while (i * i + q * q >= n * n && q >= 0) q--;
		if (q == -1) a[++m] = make_pair(p + 1, 0);
		else a[++m] = make_pair(q + 1, p + 1);
	}
	sort(a + 1, a + m + 1);
	int ans = 0;
	for (int k = 0; k <= n; k++) {
		memset(dp, 0, sizeof(dp)), dp[0][0] = 1;
		for (int i = 1, f = 0, g = 0; i <= m; f += a[i].second != 0, g += a[i].second == 0, i++)
		for (int j = 0; j <= k; j++) {
			int tmp = dp[i - 1][j];
			if (a[i].second == 0) update(dp[i][j], 1ll * tmp * (a[i].first - j - g) % P);
			else {
				if (j != k) update(dp[i][j + 1], 1ll * tmp * (a[i].first - j - g) % P);
				update(dp[i][j], 1ll * tmp * (a[i].second - k - n - (f - j)) % P);
			}
		}
		int now = dp[m][k];
		if (k & 1) update(ans, P - now);
		else update(ans, now);
	}
	writeln(ans % Q);
	return 0;
}

Atcoder Grand Contest 37

Problem D. Sorting a Grid

输入的每一行的顺序是无关的，因此，可以将输入描述为 $N\times M$ 个二元组 $(x_i,y_i)$ ，即 $i$ 在 $S,T$ 中出现的行号 $x_i,y_i$ 。

我们需要将 $i$ 分配在 $B$ 的第 $x_i$ 行， $C$ 的第 $y_i$ 行，并且使它们在同一列。

考虑构建如下二分图，对于每一个 $i$ ，连接左侧第 $x_i$ 个点和右侧第 $y_i$ 个点，则左侧与右侧每一个点的度数均为 $M$ ，由 $Hall$ 定理，该图存在完美匹配。

因此，找到一个匹配用于填第一列，删掉对应的边，重复该过程即可。

时间复杂度 $O(N^3\sqrt{N})$ ，其中 $N,M$ 同阶。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 105;
const int MAXM = 1e4 + 5;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int n, m, s, res[MAXN];
bool mat[MAXN][MAXN];
namespace NetworkFlow {
	const int INF = 2e9;
	const int MAXP = 205;
	struct edge {
		int dest, flow;
		unsigned pos;
	};
	vector <edge> a[MAXP];
	int tot, s, t, dist[MAXP];
	unsigned curr[MAXP];
	void addedge(int x, int y, int z) {
		a[x].push_back((edge) {y, z, a[y].size()});
		a[y].push_back((edge) {x, 0, a[x].size() - 1});
	}
	void init() {
		for (int i = 1; i <= n; i++) {
			a[i].clear();
			a[i + n].clear();
		}
		a[s = 2 * n + 1].clear();
		a[t = 2 * n + 2].clear();
		for (int i = 1; i <= n; i++) {
			addedge(s, i, 1);
			addedge(i + n, t, 1);
		} 
		for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (mat[i][j]) addedge(i, j + n, 1);
	}
	int dinic(int pos, int limit) {
		if (pos == t) return limit;
		int used = 0, tmp;
		for (unsigned &i = curr[pos]; i < a[pos].size(); i++)
			if (a[pos][i].flow != 0 && dist[pos] + 1 == dist[a[pos][i].dest] && (tmp = dinic(a[pos][i].dest, min(limit - used, a[pos][i].flow)))) {
				used += tmp;
				a[pos][i].flow -= tmp;
				a[a[pos][i].dest][a[pos][i].pos].flow += tmp;
				if (used == limit) return used;
			}
		return used;
	}
	bool bfs() {
		static int q[MAXP];
		int l = 0, r = 0;
		memset(dist, 0, sizeof(dist));
		dist[s] = 1, q[0] = s;
		while (l <= r) {
			int tmp = q[l];
			for (unsigned i = 0; i < a[tmp].size(); i++)
				if (dist[a[tmp][i].dest] == 0 && a[tmp][i].flow != 0) {
					q[++r] = a[tmp][i].dest;
					dist[q[r]] = dist[tmp] + 1;
				}
			l++;
		}
		return dist[t] != 0;
	}
	void flow() {
		int ans = 0;
		while (bfs()) {
			memset(curr, 0, sizeof(curr));
			ans += dinic(s, INF);
		}
		assert(ans == n);
		for (int i = 1; i <= n; i++) {
			for (auto x : a[i]) {
				if (x.dest != s && x.flow == 0) res[i] = x.dest - n;
			}
		}
	}
}
int a[MAXN][MAXN], b[MAXN][MAXN];
int f[MAXN][MAXN], g[MAXN][MAXN];
pair <int, int> home[MAXM];
vector <int> e[MAXN][MAXN]; 
int main() {
	read(n), read(m);
	for (int i = 1; i <= n; i++)
	for (int j = 1; j <= m; j++) {
		read(a[i][j]);
		home[a[i][j]].first = i;
		b[i][j] = ++s;
		home[b[i][j]].second = i;
	}
	for (int i = 1; i <= n * m; i++)
		e[home[i].first][home[i].second].push_back(i);
	for (int k = 1; k <= m; k++) {
		for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			mat[i][j] = e[i][j].size() != 0;
		NetworkFlow :: init();
		NetworkFlow :: flow();
		for (int i = 1; i <= n; i++) {
			int tmp = e[i][res[i]].back();
			e[i][res[i]].pop_back();
			f[i][k] = tmp;
			g[res[i]][k] = tmp;
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++)
			printf("%d ", f[i][j]);
		printf("n");
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++)
			printf("%d ", g[i][j]);
		printf("n");
	}
	return 0;
}

Problem E. Reversing and Concatenating

令字符串中出现的最小的字符为 $Min$ ，考虑答案串开头 $Min$ 的个数 $Len$ 。

若字符串最后一个字符为 $Min$ ，连续长度为 $L$ ，则 $Len$ 应当与 $L\times 2^K$ 取最大值。

令字符串中间最长的一段字符 $Min$ 长度为 $L$ ，则 $Len$ 应当与 $L\times 2^{K-1}$ 取最大值。

使得 $Len$ 取到最大值的方式只有每一次操作使得末尾处的 $Min$ 的长度翻倍。

在所有可能使得 $Len$ 取到最大值的方式中取答案字典序最小的一种即可。

时间复杂度 $O(N^2)$ 。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e4 + 5;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int n, k;
char Min, Max, ans[MAXN], s[MAXN];
void check(char *s, int k) {
	static char t[MAXN];
	int now = n, len = 0;
	while (now >= 1 && s[now] == Min) now--, len++;
	assert(len != 0);
	while (k != 0 && len < n) len *= 2, k--;
	if (len >= n) {
		for (int i = 1; i <= n; i++)
			ans[i] = Min;
		printf("%sn", ans + 1);
		exit(0);
	}
	for (int i = 1; i <= len; i++)
		t[i] = Min;
	for (int i = len + 1; i <= n; i++)
		t[i] = s[now--];
	for (int i = 1; i <= n; i++)
		if (t[i] < ans[i]) {
			for (int j = 1; j <= n; j++)
				ans[j] = t[j];
			return;
		} else if (t[i] > ans[i]) return;
}
int main() {
	read(n), read(k);
	scanf("%s", s + 1);
	Min = 'z', Max = 'a';
	for (int i = 1; i <= n; i++) {
		chkmin(Min, s[i]);
		chkmax(Max, s[i]);
		s[2 * n - i + 1] = s[i];
		ans[i] = 'z';
	}
	if (Min == Max) {
		printf("%sn", s + 1);
		return 0;
	}
	if (s[n] == Min) check(s, k);
	for (int i = n; i <= 2 * n; i++)
		if (s[i] == Min) check(s + i - n, k - 1);
	printf("%sn", ans + 1);
	return 0;
}

Problem F. Counting of Subarrays

考虑如何判定一个序列合法。

首先，若序列长度为 $1$ ，序列合法。

若序列仅包含一种元素，当且仅当序列长度 $\ge L$ ，序列合法。

否则，取一段极长的仅包含最小值 $Min$ 的区间 $[l_i,r_i]$ ，则要求 $r_i-l_i+1\ge L$ ，并且以 $\lfloor \frac{r_i-l_i+1}{L}\rfloor$ 个 $Min+1$ 代替之得到的序列合法。

将问题拓展一下，为每一个位置指定两个数 $X_i,Y_i$ ，对于所有合法区间 $[l,r]$ ，求 $X_l\times Y_r$ 的和。

考虑上面的判断合法的过程，实际上我们可以将每一个区间放在一起考虑。

即每次处理序列中现存的最小值 $Min$ 所在的位置，并计算新产生的 $Min+1$ 对应的 $X_i,Y_i$ 。

考虑一段最小值 $Min$ 产生的 $Min+1$ 对应的 $X_i,Y_i$ ，第 $1,2,\dots ,L-1$ 个元素显然不能作为区间的右端点，不对 $Y_i$ 产生贡献； $L,L+1,\dots ,2L-1$ 个元素作为区间的右端点可以产生一个 $Min+1$ ，对 $Y_1$ 产生贡献； $2L,2L+1,\dots ,3L-1$ 个元素作为区间的右端点可以产生两个 $Min+1$ ，对 $Y_2$ 产生贡献，以此类推， $X_i$ 同理。

具体细节建议参考代码，时间复杂度 $O(NLogN)$ 。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int n, l, x[MAXN];
pair <int, int> y[MAXN];
ll calc(vector <pair <int, int>> &a) {
	ll ans = 0, sum = 0;
	for (unsigned i = l - 1, j = 0; i < a.size(); i++, j++) {
		sum += a[j].first;
		ans += a[i].second * sum;
	}
	return ans;
}
int main() {
	read(n), read(l);
	for (int i = 1; i <= n; i++) {
		read(x[i]);
		y[i] = make_pair(x[i], i);
	}
	sort(y + 1, y + n + 1); ll ans = n; int val = 0, pos = 1;
	vector <pair <pair <int, int>, pair <int, int>>> a, b;
	while (true) {
		if (a.empty()) {
			if (pos > n) break;
			else val = y[pos].first;
		} else val++;
		while (val == y[pos].first) a.emplace_back(make_pair(y[pos].second, y[pos].second), make_pair(1, 1)), pos++;
		b.clear(), sort(a.begin(), a.end());
		for (unsigned i = 0, j; i < a.size(); i = j + 1) {
			j = i; while (j + 1 < a.size() && a[j + 1].first.first == a[j].first.second + 1) j++;
			int len = j - i + 1, cnt = len / l;
			if (cnt != 0) {
				vector <pair <int, int>> cur, where, value;
				for (unsigned k = i; k <= j; k++)
					cur.push_back(a[k].second);
				ans += calc(cur);
				for (int k = 1; k <= cnt; k++) {
					where.emplace_back(a[i].first.first + k - 1, (k == cnt) ? a[j].first.second : a[i].first.first + k - 1);
					value.emplace_back(0, 0);
				}
				for (unsigned k = i; k <= j; k++) {
					int tl = k - i + 1, tr = j - k + 1;
					if (tl >= l) value[tl / l - 1].second += a[k].second.second;
					if (tr >= l) value[cnt - tr / l].first += a[k].second.first;
				}
				ans -= calc(value);
				for (unsigned k = 0; k < where.size(); k++)
					b.emplace_back(where[k], value[k]);
			} 
		}
		a = b;
	}
	writeln(ans);
	return 0;
}

Atcoder Grand Contest 38

Problem E. Gachapon

考虑计算到达各个尚未完成的状态的概率之和，由期望的线性性，这也是答案。

令所有状态的指数型生成函数为 $G(x)$ ，普通型生成函数为 $g(x)$ ，已经完成的状态的指数型生成函数为 $F(x)$ ，普通型生成函数为 $f(x)$ ，那么我们要求的就是 $g(1)-f(1)$ 。

考虑计算 $H(x)=G(x)-F(x)$ ，令 $p_i=\frac{A_i}{\sum A_i}$ ，有
$$H(x)=e^x-\prod _{i=1}^N(e^{p_{i}x}-1-p_{i}x-\frac{p_i^2{x}^2}{2}-\cdots -\frac{p_i^{B_i-1}{x}^{B_i-1}}{(B_i-1)!})$$

令 $SA=\sum A_i,y=e^{\frac{1}{SA}x}$ ，那么
$$H(x)=y^{SA}-\prod _{i=1}^N(y^{A_i}-1-p_{i}x-\frac{p_i^2{x}^2}{2}-\cdots -\frac{p_i^{B_i-1}{x}^{B_i-1}}{(B_i-1)!})$$

暴力展开 $H(x)$ 的计算式，对于各个 $y^i$ ，展开关于 $x$ 的多项式的时间复杂度均为 $O((\sum B_i{)}^2)$ ，因此展开的时间复杂度为 $O((\sum A_i)\times (\sum B_i{)}^2)$ 。

接下来考虑如何将 $H(x)$ 转为普通型生成函数求出 $h(1)$ 。

对于形如 $c{y}^i$ 的项，其对答案的贡献显然为
$$\frac{c}{1-\frac{i}{SA}}$$

考虑形如 $c{y}^i{x}^j$ 的项，其对答案的贡献应当为
$$c\sum _{k=0}^{\infty }(\frac{i}{SA}{)}^k\times (k+1)\times (k+2)\times \cdots \times (k+j)$$

考虑对于 $0<p<1,i\in \mathbb{N}$ ，计算
$$S=\sum _{k=0}^{\infty }{p}^k\times k^i$$

等式两侧同时乘以 $p$ ，则有
$$pS=\sum _{k=0}^{\infty }{p}^{k+1}\times k^i$$

那么
$$(1-p)S=[i=0]+\sum _{k=0}^{\infty }{p}^{k+1}\times ((k+1{)}^i-k^i)$$

将 $(k+1{)}^i$ 用二项式定理展开，即可将问题递归至更小的规模。

本部分时间复杂度也为 $O((\sum A_i)\times (\sum B_i{)}^2)$ 。

总时间复杂度 $O((\sum A_i)\times (\sum B_i{)}^2)$ 。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 405;
const int P = 998244353;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int n, sa, sb, a[MAXN], b[MAXN];
int f[MAXN][MAXN], g[MAXN], coef[MAXN][MAXN];
int fac[MAXN], inv[MAXN], binom[MAXN][MAXN];
int power(int x, int y) {
	if (y == 0) return 1;
	int tmp = power(x, y / 2);
	if (y % 2 == 0) return 1ll * tmp * tmp % P;
	else return 1ll * tmp * tmp % P * x % P;
}
void update(int &x, int y) {
	x += y;
	if (x >= P) x -= P;
}
int main() {
	read(n), sa = 0, f[0][0] = 1;
	for (int i = 1; i <= n; i++) {
		read(a[i]), read(b[i]);
		sa += a[i], sb += b[i];
	}
	fac[0] = inv[0] = binom[0][0] = 1;
	for (int i = 1; i <= max(sa, sb); i++) {
		fac[i] = 1ll * fac[i - 1] * i % P;
		inv[i] = power(fac[i], P - 2);
		binom[i][0] = 1;
		for (int j = 1; j <= i; j++) {
			binom[i][j] = (binom[i - 1][j - 1] + binom[i - 1][j]) % P;
		}
	}
	for (int x = 1, s = 0; x <= n; s += b[x++]) {
		memset(g, 0, sizeof(g));
		int p = 1ll * a[x] * power(sa, P - 2) % P;
		for (int i = 0, now = 1; i <= b[x] - 1; i++, now = 1ll * now * p % P)
			g[i] = (P - 1ll * now * inv[i] % P) % P;
		for (int i = sa; i >= 0; i--) {
			static int tmp[MAXN];
			memset(tmp, 0, sizeof(tmp));
			for (int j = 0; j <= b[x]; j++)
			for (int k = 0; k <= s; k++) {
				update(tmp[j + k], 1ll * f[i][k] * g[j] % P);
			}
			memcpy(f[i], tmp, sizeof(tmp));
			if (i >= a[x]) {
				for (int j = 0; j <= s; j++)
					update(f[i][j], f[i - a[x]][j]);
			}
		}
	}
	assert(f[sa][0] == 1);
	int ans = 0;
	for (int i = 0; i <= sb; i++)
		update(ans, 1ll * f[0][i] * fac[i] % P);
	coef[0][0] = 1;
	for (int i = 1; i <= sb; i++)
	for (int j = i; j >= 0; j--) {
		coef[i][j] = 1ll * coef[i - 1][j] * i % P;
		if (j != 0) update(coef[i][j], coef[i - 1][j - 1]);
	}
	for (int i = 1; i <= sa - 1; i++) {
		static int res[MAXN];
		int p = 1ll * i * power(sa, P - 2) % P;
		memset(res, 0, sizeof(res)), res[0] = power((1 - p + P) % P, P - 2);
		for (int j = 1; j <= sb; j++) {
			int tmp = 0;
			for (int k = 0; k <= j - 1; k++)
				update(tmp, 1ll * binom[j][k] * res[k] % P);
			res[j] = 1ll * tmp * p % P * res[0] % P;
		}
		for (int j = 0; j <= sb; j++) {
			int tmp = 0;
			for (int k = 0; k <= j; k++)
				update(tmp, 1ll * res[k] * coef[j][k] % P);
			update(ans, 1ll * tmp * f[i][j] % P);
		}
	}
	writeln((P - ans) % P);
	return 0;
}

Problem F. Two Permutations

将输入的排列 $P,Q$ 看做两个置换，则其各个环或是整体被改为连向自身，或是不作修改。

注意到时间限制对于 $10^5$ 的数据规模来说异常地大，考虑用最小割解题。

对于一个位置 $i$ ，有如下几种情况：
$(1)$ 、 $P_i=Q_i=i$ ：此时无论是否改变都不会对答案造成影响。
$(2)$ 、 $P_i=Q_i\ne i$ ：此时只改变 $P,Q$ 中的一个可以使答案 $+1$ 。
$(3)$ 、 $P_i=i\ne Q_i$ ：此时改变 $Q$ 会使得答案 $-1$ 。
$(4)$ 、 $Q_i=i\ne P_i$ ：此时改变 $P$ 会使得答案 $-1$ 。
$(5)$ 、 $，，P_i，Q_i，i$ 互不相同：同时改变 $P,Q$ 会使得答案 $-1$ 。

由于要使用最小割解题，我们不希望出现增益的条件，考虑对 $(2)$ 稍作修改。
$(2)$ 、 $P_i=Q_i\ne i$ ：此时不改变 $P,Q$ ，或同时改变 $P,Q$ 会使得答案 $-1$ 。

对于 $P$ 中的点，令将其划分在 $S$ 集表示改变，划分在 $T$ 集表示不改变；对于 $Q$ 中的点，令将其划分在 $T$ 集表示改变，划分在 $S$ 集表示不改变。

那么对于上面的情况，我们分别可以按照如下方式连边。
$(2)$ 、 $P\leftrightarrow Q$
$(3)$ 、 $S\to Q$
$(4)$ 、 $P\to T$
$(5)$ 、 $P\to Q$

时间复杂度 $O(Dinic(N,N))$ 。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
const int INF = 2e9;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
namespace NetworkFlow {
	const int INF = 2e9;
	const int MAXP = 5e5 + 5;
	struct edge {
		int dest, flow;
		unsigned pos;
	};
	vector <edge> a[MAXP];
	int tot, s, t, dist[MAXP];
	unsigned curr[MAXP];
	void addedge(int x, int y, int z) {
		a[x].push_back((edge) {y, z, a[y].size()});
		a[y].push_back((edge) {x, 0, a[x].size() - 1});
	}
	int dinic(int pos, int limit) {
		if (pos == t) return limit;
		int used = 0, tmp;
		for (unsigned &i = curr[pos]; i < a[pos].size(); i++)
			if (a[pos][i].flow != 0 && dist[pos] + 1 == dist[a[pos][i].dest] && (tmp = dinic(a[pos][i].dest, min(limit - used, a[pos][i].flow)))) {
				used += tmp;
				a[pos][i].flow -= tmp;
				a[a[pos][i].dest][a[pos][i].pos].flow += tmp;
				if (used == limit) return used;
			}
		return used;
	}
	bool bfs() {
		static int q[MAXP];
		int l = 0, r = 0;
		memset(dist, 0, sizeof(dist));
		dist[s] = 1, q[0] = s;
		while (l <= r) {
			int tmp = q[l];
			for (unsigned i = 0; i < a[tmp].size(); i++)
				if (dist[a[tmp][i].dest] == 0 && a[tmp][i].flow != 0) {
					q[++r] = a[tmp][i].dest;
					dist[q[r]] = dist[tmp] + 1;
				}
			l++;
		}
		return dist[t] != 0;
	}
	int flow() {
		int ans = 0;
		while (bfs()) {
			memset(curr, 0, sizeof(curr));
			ans += dinic(s, INF);
		}
		return ans;
	}
}
int n, a[MAXN], b[MAXN];
int va[MAXN], vb[MAXN];
int main() {
	int n; read(n);
	for (int i = 1; i <= n; i++)
		read(a[i]), a[i]++;
	for (int i = 1; i <= n; i++)
		read(b[i]), b[i]++;
	for (int i = 1; i <= n; i++) {
		if (va[i]) continue;
		int pos = i;
		while (va[pos] == 0) {
			va[pos] = i;
			pos = a[pos];
		}
	}
	for (int i = 1; i <= n; i++) {
		if (vb[i]) continue;
		int pos = i;
		while (vb[pos] == 0) {
			vb[pos] = i + n;
			pos = b[pos];
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++)
		ans += a[i] != b[i];
	int s = NetworkFlow :: s = 2 * n + 1;
	int t = NetworkFlow :: t = 2 * n + 2;
	for (int i = 1; i <= n; i++) {
		if (a[i] == b[i]) {
			if (a[i] == i) continue; ans += 1;
			NetworkFlow :: addedge(vb[i], va[i], 1);
			NetworkFlow :: addedge(va[i], vb[i], 1);
		} else {
			if (a[i] == i) NetworkFlow :: addedge(s, vb[i], 1);
			else if (b[i] == i) NetworkFlow :: addedge(va[i], t, 1);
			else NetworkFlow :: addedge(va[i], vb[i], 1);
		}
	}
	ans -= NetworkFlow :: flow();
	writeln(ans);
	return 0;
}

Atcoder Grand Contest 39

Problem D. Incenters

"I prefer solving problems about world history rather than MO geometry."

对于选定的三个点 $A,B,C$ ，令 $A^{\prime }$ 为不经过 $A$ 的圆弧 $BC$ 的中点， $B^{\prime },C^{\prime }$ 同理。

可以证明， $△ABC$ 的内心与 $△A^{\prime }{B}^{\prime }{C}^{\prime }$ 的重心重合。

而在 $△A^{\prime }{B}^{\prime }{C}^{\prime }$ 中，考虑三角形的 欧拉线 ，令外心为 $O$ ，中心为 $G$ ，重心为 $H$ ，则 $H$ 在 $OG$ 的延长线上，并且 $|HG|=2|OG|$ 。原题中，显然 $O=(0,0)$ ，因此若能计算出 $G$ 坐标的期望，便能计算出 $H$ 坐标的期望

显然 $G=\frac{A^{\prime }+B^{\prime }+C^{\prime }}{3}$ ，因此只需要枚举两个点计算 $A^{\prime }$ 的贡献即可。

时间复杂度 $O(N^2)$ 。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
const double pi = acos(-1);
const double eps = 1e-10;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
double a[MAXN];
int main() {
	int n, l; read(n), read(l);
	for (int i = 1; i <= n; i++)
		read(a[i]);
	double ansx = 0, ansy = 0;
	for (int i = 1; i <= n; i++)
	for (int j = i + 1; j <= n; j++) {
		ansx += cos(pi * (a[i] + a[j]) / l) * (n - (j - i + 1));
		ansy += sin(pi * (a[i] + a[j]) / l) * (n - (j - i + 1));
		ansx += cos(pi * (a[i] + a[j] + l) / l) * (j - i - 1);
		ansy += sin(pi * (a[i] + a[j] + l) / l) * (j - i - 1);
	}
	double cnt = 1.0 * n * (n - 1) * (n - 2) / 6;
	printf("%.10lf %.10lfn", ansx / cnt, ansy / cnt);
	return 0;
}

Problem E. Pairing Points

首先考虑与 $1$ 配对的点，不妨令为点 $i$ 。

那么，我们需要对 $[2,i)\cup (i,N]$ 继续配对，并且，横跨两个区间的边至少要有一条，若有多条，则需要满足它们的端点之间存在单调性，即保证连线不成环。

考虑枚举最靠外侧的横跨两个区间的边 $(j,k)$ 。

$(j,i)$ 之间的点或是与 $j$ 连通，或是与 $i$ 连通，并且存在一个分界线，考虑枚举它，记为 $p$ ，同理，枚举与 $i$ 或 $k$ 连通的分界线 $q$ 。

由于 $(j,k)$ 是最靠外侧的横跨两个区间的边，因此，对于区间 $[2,p]$ 内的点，我们不再需要知晓区间 $[i,N]$ 内的信息，从而递归为了一个点集 $[2,j)\cup (j,p]$ 的子问题。同理， 区间 $[q,N]$ 内的点递归为了一个点集 $[q,k)\cup (k,N]$ 的子问题，而剩余的点则递归为了一个点集 $[p+1,i)\cup (i,q-1]$ 的子问题。

由此进行动态规划，时间复杂度 $O(N^7)$ 。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 55;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
char s[MAXN][MAXN];
ll dp[MAXN][MAXN][MAXN];
ll getans(int l, int r, int m) {
	if (dp[l][r][m] != -1) return dp[l][r][m];
	if (l == r) return dp[l][r][m] = 1;
	if (l == m || r == m) return dp[l][r][m] = 0;
	ll &res = dp[l][r][m]; res = 0;
	for (int i = l; i <= m - 1; i++)
	for (int j = m + 1; j <= r; j++) {
		if (s[i][j] == '0') continue;
		for (int s = i; s <= m - 1; s++)
		for (int t = m + 1; t <= j; t++)
			res += getans(l, s, i) * getans(s + 1, t - 1, m) * getans(t, r, j);
	}
	return res;
}
int main() {
	int n; read(n);
	for (int i = 1; i <= n * 2; i++)
		scanf("n%s", s[i] + 1);
	memset(dp, -1, sizeof(dp));
	ll ans = 0;
	for (int i = 2; i <= n * 2; i++)
		if (s[1][i] == '1') ans += getans(2, n * 2, i);
	writeln(ans);
	return 0;
}

Problem F. Min Product Sum

考虑一个矩阵权值的组合意义，可以认为除了矩阵 $A$ 外，我们还填写了矩阵 $B$ ，并且，矩阵 $B$ 各行各列的最大值不超过矩阵 $A$ 对应行列的最小值，求总方案数。

令矩阵 $B$ 各行的最大值为 $X_i$ ，矩阵 $A$ 各列的最小值为 $Y_i$ 。

我们希望得到一个动态规划解法，而状态实际上已经确定，应当为已经确定的行数 $i$ 、列数 $j$ 、数字数 $k$ ，即状态数是 $O(NMK)$ 级别的。因此，我们需要一个线性的转移，但是，若状态 $i,j$ 都是用来描述矩阵 $A$ 的，在转移时，我们就不得不枚举两维进行转移，从而超过了需要的线性复杂度。

由此，可以想到用其中一个状态描述 $A$ ，另一个状态描述 $B$ 。

记 $d{p}_{i,j,k}$ 表示已经考虑了 $X_i\le k$ 的 $i$ 行和 $Y_i\le k$ 的 $j$ 列，此时已经确定的数的填法总数。

转移时首先考虑枚举 $X_i=k+1$ 的行数，对于每一个这样的行，可以在已经确定 $Y_i\le k$ 的 $j$ 列填上 $\ge k+1$ 的 $A$ 中的元素，并在尚未确定 $Y_i\le k$ 的 $M-j$ 列填上 $\le k+1$ 的 $B$ 中的元素，并保证至少有一个填入的数 $=k+1$ 。

再考虑枚举 $Y_i=k+1$ 的列数，对于每一个这样的列，可以在已经确定 $X_i\le k$ 的 $i$ 行填上 $\ge k+1$ 的 $A$ 中的元素，并保证至少有一个填入的数 $=k+1$ ，并在尚未确定 $X_i\le k$ 的 $N-i$ 行填上 $\le k$ 的 $B$ 中的元素。

不难发现上述两个转移可以认为是转移的两个阶段，因此，只需要给状态加一维 $0/1$ 即可。

预处理转移系数，时间复杂度 $O(NMK(N+M))$ 。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 105;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int n, m, k, P, dp[MAXN][MAXN][MAXN][2];
int binom[MAXN][MAXN], coef[MAXN][MAXN][MAXN][2];
void update(int &x, int y) {
	x += y;
	if (x >= P) x -= P;
}
int power(int x, int y) {
	if (y == 0) return 1;
	int tmp = power(x, y / 2);
	if (y % 2 == 0) return 1ll * tmp * tmp % P;
	else return 1ll * tmp * tmp % P * x % P;
}
int main() {
	read(n), read(m), read(k), read(P), dp[1][0][0][0] = 1;
	for (int i = 0; i <= max(n, m); i++) {
		binom[i][0] = 1;
		for (int j = 1; j <= i; j++)
			binom[i][j] = (binom[i - 1][j - 1] + binom[i - 1][j]) % P;
	}
	for (int t = 1; t <= k; t++)
	for (int i = 0; i <= m; i++) {
		for (int j = 0; j <= n; j++) {
			int tmp = (power(t, m - i) - power(t - 1, m - i) + P) % P;
			tmp = 1ll * tmp * power(k - t + 1, i) % P;
			coef[t][i][j][0] = power(tmp, j);
		}
	}
	for (int t = 1; t <= k; t++)
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			int tmp = (power(k - t + 1, i) - power(k - t, i) + P) % P;
			tmp = 1ll * tmp * power(t, n - i) % P;
			coef[t][i][j][1] = power(tmp, j);
		}
	}
	for (int t = 1; t <= k; t++) {
		for (int i = 0; i <= n; i++)
		for (int j = 0; j <= m; j++) {
			int tmp = dp[t][i][j][0];
			for (int k = 0; i + k <= n; k++)
				update(dp[t][i + k][j][1], 1ll * tmp * binom[n - i][k] % P * coef[t][j][k][0] % P);
			tmp = dp[t][i][j][1];
			for (int k = 0; j + k <= m; k++)
				update(dp[t + 1][i][j + k][0], 1ll * tmp * binom[m - j][k] % P * coef[t][i][k][1] % P);
		}
	}
	writeln(dp[k + 1][n][m][0]);
	return 0;
}

最后

以上就是尊敬钢铁侠为你收集整理的【集训队作业】IOI 2020 集训队作业 试题泛做 4Atcoder Grand Contest 35Atcoder Grand Contest 36Atcoder Grand Contest 37Atcoder Grand Contest 38Atcoder Grand Contest 39的全部内容，希望文章能够帮你解决【集训队作业】IOI 2020 集训队作业 试题泛做 4Atcoder Grand Contest 35Atcoder Grand Contest 36Atcoder Grand Contest 37Atcoder Grand Contest 38Atcoder Grand Contest 39所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。