https://codeforces.com/contest/1327

D. Infinite Path

 

题意：定义排列的乘法：c=a×b  ⟹  c[i]=b[a[i]]c = a \times b\implies c[i] = b[a[i]]。定义一种特殊路径：i,p[i],p[p[i]],p[p[p[i]]]…i, p[i], p[p[i]], p[p[p[i]]] \dots，且路径上所有点颜色相同。给定排列 pp，求最小的 kk 使得 pkp^k 中存在一条这样的特殊路径。

容易想到转成有向图，每个点出度入度都为1，一定是几个不相交的环。然后根据离散数学的知识，或者画图看出来， pkp^k 就是把 pp 中 uu 指向 vv 的边变成 uu 指向 vv 顺时针后 kk 位的点。

那么就是要找到最小的 kk ，使得在原图上的某个环里，存在一个公差为 kk 的等差数列，且数列里的所有点颜色相同。

最关键的一点是， kk 一定是最终答案所在环的长度的因数，因为如果不是因数，最终的间隔数一定在枚举因数的时候枚举过了，

那么复杂度就可以降到 O(nn)\mathcal{O}(n \sqrt n)。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int T;
int n, p[N], c[N];
int vis[N], cir[N], len;
bool check(int l) {
	for (int i = 0; i < l; i++) {
		bool ok = 1;
		int u = i;
		while ((u + l) % len != i) {
			if (c[cir[u]] != c[cir[i]])ok = 0;
			u = (u + l) % len;
		}
		if (c[cir[u]] != c[cir[i]])ok = 0;
		if (ok)return true;
	}
	return false;
}
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		fill(vis + 1, vis + n + 1, 0);
		int ans = INF;
		for (int i = 1; i <= n; i++)scanf("%d", &p[i]);
		for (int i = 1; i <= n; i++)scanf("%d", &c[i]);
		for (int i = 1; i <= n; i++) {
			if (vis[i])continue;
			int u = i; len = 0;
			while (p[u] != i) {
				cir[len++] = u;
				vis[u] = 1;
				u = p[u];
			}
			cir[len++] = u; vis[u] = 1;
			for (int j = 1; j*j <= len; j++) {
				if (len%j)continue;
				if (check(j))ans = min(ans, j);
				if (check(len / j))ans = min(ans, len / j);
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

 

E. Count The Blocks

 

题意：写下 00 到 10n−110^n-1 的所有数，且补前导0，使得每个数长度都为 nn，对 ii 从 11 到 nn，不考虑不同数之间，问写下的数字中有多少的长为 ii 的连续相等数块。

既然每一位都能从0写到9，那么每个数就是一样的了，可以算0的值，再乘10.

长度为 ii 的块有 n−i+1n-i+1 个，放入1块后，剩下 n−in-i 位，其中与块相邻的两位有9种取法，其他的有10种取法。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const ll mod = 998244353;
ll fact[N], inv[N];
ll power(ll a, ll x) {
	ll ans = 1;
	while (x) {
		if (x & 1) ans = (ans * a) % mod;
		a = (a * a) % mod;
		x >>= 1;
	}
	return ans;
}
int main() {
	scanf("%lld", &n);
	init();
	for (ll i = 1; i <= n; i++) {
		if (i == n) { printf("10\n"); }
		else if (i == n - 1)printf("180 ");
		else{
			ll ans = (power(10, n - i - 1) * 180) % mod;
			ans = (ans + (n - i - 1) * 9 * 9 * 10 % mod*power(10, n - i - 2) % mod) % mod;
			printf("%lld ", ans);
		}
	}
	return 0;
}