https://codeforces.com/contest/1151

E. Number of Components

 

题意：给定一条链，编号从1到n，每点有颜色，f(L,R)f(L,R) 为颜色在 [L,R][L,R] 的点的点导出子图上联通块的个数，问所有区间的 f 值之和。

dp/计数

和上一场Atcoder的几乎一样，但是这里是一条链，并且每种颜色的点数不固定。

当然可以用并查集把相邻的颜色相同的点合起来，再同样做法遍历颜色，只不过这里每次加入的可能不止一个点。

思路相同，但是其实本题更简单，可以直接计数。

假设是一条横着的链，每个点与它左边的点相连。则如果某个区间时该点左边的点也在这个区间里，则可以视为该点与左边的点合并了。

则遍历每个点，每次考虑加入这个颜色会使得所有区间的 f 值增加多少。

对于同时包含了它和它左边点的区间，联通块个数不会增加；对于不包含它的区间，当然也不会增加；对于只包含它，而不包含它左边点的区间，联通块个数+1。

则只要遍历每点，找到只包含它，而不包含它左边点的颜色区间的个数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 1e5 + 10;
int n;
ll a[N];
ll ans;
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)scanf("%lld", &a[i]);
	ans = a[1] * (n - a[1] + 1);
	for (int i = 2; i <= n; i++) {
		if (a[i] > a[i - 1])ans += (a[i] - a[i - 1])*(n - a[i] + 1);
		else if (a[i] < a[i - 1])ans += a[i] * (a[i - 1] - a[i]);
	}
	printf("%lld\n", ans);
	return 0;
}

 

F. Sonya and Informatics

 

题意：给定一个01序列，每次操作等可能地选2个位置交换，问 k 次操作后序列递增的概率。

dp+矩阵快速幂

最终一定是前面全是 0，后面全是 1。设总共有 c 个 0，则最终前 c 位全是 0.

设 dp[i][j]dp[i][j] 表示第 i 次操作后，前 c 位有 j 个 0 。

则最终结果为 dp[k][c]∑i=0cdp[k][i]\frac{dp[k][c]}{\sum_{i=0}^cdp[k][i]}。

可能由 dp[i−1][j−1],dp[i−1][j],dp[i−1][j+1]dp[i - 1][j - 1],dp[i - 1][j],dp[i - 1][j + 1] 转移得到。

0 增加只可能是后 n-c 位的 0 与前 c 位的 1 交换，0 减少类似。

0 不变可能是 00 交换，11 交换，前 c 位内部交换，后 n-c 位内部交换。

所以得到一个 n*k 的循环，还要优化。

dp只与 i-1 的dp，以及 j，n，c 有关，而且可以通过压缩变成一维的，所以可以通过 k 次类似的转移得到最终结果。

则考虑把 {dp[0],dp[1],dp[2],⋯ ,dp[c]}\{dp[0],dp[1],dp[2],\cdots,dp[c]\} 作为一个向量，乘以一个转移矩阵A的 k 次幂，得到最终的值，也就是 dp[k][0,1,⋯ ,c]dp[k][0,1,\cdots,c]。

转移矩阵A是 (c+1)∗(c+1)(c+1)*(c+1) 维的。

用矩阵快速幂优化dp还是第一次遇到，要注意一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 110;
struct Mat {
	int a[N][N];
	int r, c;
	Mat(int _r, int _c) { r = _r, c = _c, memset(a, 0, sizeof(a)); }
};
Mat operator * (Mat X, Mat Y) {
	Mat Z(X.r, Y.c);
	for (int i = 0; i < X.r; ++i) {
		for (int j = 0; j < Y.c; ++j) {
			for (int k = 0; k < X.c; ++k) {
				Z.a[i][j] = (Z.a[i][j] + 1ll * X.a[i][k] * Y.a[k][j] % mod) % mod;
			}
		}
	}
	return Z;
}
Mat pow(Mat a, ll n) {
	Mat res(a.r, a.c);
	for (int i = 0; i < a.r; i++)
		res.a[i][i] = 1;
	while (n) {
		if (n & 1) res = res * a;;
		a = a * a;
		n >>= 1;
	}
	return res;
}
ll Pow(ll a, ll b) {
	ll res = 1ll;
	while (b) {
		if (b & 1)res = res * a%mod;
		a = a * a%mod;
		b >>= 1;
	}
	return res;
}
int n, k;
int a[N], c, x;
int main() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		c += (a[i] == 0);
	}
	for (int i = 1; i <= c; i++)x += (a[i] == 0);
	Mat dp(c + 1, 1);
	Mat A(c + 1, c + 1);
	dp.a[x][0] = 1;
	for (int i = 0; i <= c; i++) {
		if (i > 0)A.a[i][i - 1] = (c - i + 1)*(c - i + 1);
		if (i < c)A.a[i][i + 1] = (i + 1)*(n - 2 * c + i + 1);
		A.a[i][i] = c * (c - 1) / 2 + (n - c)*(n - c - 1) / 2 + i * (c - i) + (c - i)*(n - 2 * c + i);
	}
	A = pow(A, k);
	dp = A * dp;
	ll tmp = 0ll;
	for (int i = 0; i <= c; i++)tmp = (tmp + dp.a[i][0]) % mod;
	printf("%lld\n", dp.a[c][0] * Pow(tmp, mod - 2) % mod);
	return 0;
}