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内容请搜索靠谱客的其他文章。