CF1541
A 求一个排列，使得没有p[i] = i且最小化Σ(|p[i] - i|)
显然如果是偶数就相邻的交换，奇数就只有一组是三个轮换，剩下的两个换
B n个不同的数构成一个数组，问你有多少对i,j满足a[i] * a[j] == i + j，1e5
一开始没看到不同结果不会做。
枚举a[i]是多少，那么a[j]不会超过2 * n / a[i]，取值个数是调和级数nlogn的，再枚举a[j]，看有没有这样的i和j满足条件即可。 C 构造一个有向图，使得从1到每个点的最短路是给定的数组d，求所有边权的和的最小值。可以有负值，不能有负环重边先把点排序，按顺序连起来，够成一条单向链。
然后每两个点之间再连一条负权反向边，够成0环。这样就是最小值。 D 给你一棵树，每次可以等概率选择一个根，然后从已选的点相邻点中等概率选下一个，构成一个序列，求这个序列逆序对的期望。n <= 200 考虑每个点对。如果开始的根在某个点的子树内，那一定先到那个点。如果开始的根在这两点的路径上，或者路径上某一点的子树上，那么先到哪个点是有个概率的。 设左边有l个点，右边有r个点，先到r的概率是g[l][r]，左边已经到了l个点，右边已经到了r个点的概率是f[l][r]，那么f可以很简单的* 1/2求出来，g可以用f的前缀和求出来。 然后考虑选择的那点对上的路径，中间每个点乘根在子树内概率乘先到大的点的概率 就行了。 1 #include <bits/stdc++.h>
2
3 typedef long long LL;
4
5 const int N = 210;
6 const LL MO = 1e9 + 7, inv2 = 5e8 + 4;
7
8 struct Edge {
9 int nex, v;
10 }edge[N * 2]; int tp;
11
12 int n, e[N], siz[N], d[N], fa[N];
13 LL f[N][N], g[N][N];
14 LL ans;
15
16 LL qpow(LL a, LL b) {
17 a %= MO;
18 LL ans = 1;
19 while(b) {
20 if(b & 1) {
21 ans = ans * a % MO;
22 }
23 a = a * a % MO;
24 b = b >> 1;
25 }
26 return ans;
27 }
28
29 inline void add(int x, int y) {
30 ++tp;
31 edge[tp].v = y;
32 edge[tp].nex = e[x];
33 e[x] = tp;
34 return;
35 }
36
37 void DFS1(int x, int f) {
38 siz[x] = 1;
39 d[x] = d[f] + 1;
40 fa[x] = f;
41 for(int i = e[x]; i; i = edge[i].nex) {
42 int y = edge[i].v;
43 if(y == f) {
44 continue;
45 }
46 DFS1(y, x);
47 siz[x] += siz[y];
48 }
49 return;
50 }
51
52 void DFS2(int x, int r) {
53 for(int i = e[x]; i; i = edge[i].nex) {
54 int y = edge[i].v;
55 if(y == fa[x]) {
56 continue;
57 }
58 DFS2(y, r);
59 }
60 if(x > r) {
61 int p = x;
62 while(fa[p] != r) {
63 // cal fa[p]
64 ans += 1ll * (siz[fa[p]] - siz[p]) * g[d[fa[p]]][d[x] - d[fa[p]]] % MO;
65 ans %= MO;
66 // printf("ans += %d * %lld \n", siz[fa[p]] - siz[p], g[d[fa[p]]][d[x] - d[fa[p]]]);
67 p = fa[p];
68 }
69 ans = (ans + siz[x]) % MO;
70 // printf("ans += %d \n", siz[x]);
71 }
72 return;
73 }
74
75 int main() {
76 scanf("%d", &n);
77 for(int i = 1, x, y; i < n; i++) {
78 scanf("%d%d", &x, &y);
79 add(x, y);
80 add(y, x);
81 }
82
83 // prework
84 f[0][0] = 1;
85 for(int i = 1; i <= n; i++) {
86 f[i][0] = f[0][i] = f[0][i - 1] * inv2 % MO;
87 }
88 for(int i = 1; i <= n; i++) {
89 for(int j = 1; j <= n; j++) {
90 f[i][j] = f[i][j - 1] * inv2 + f[i - 1][j] * inv2;
91 f[i][j] %= MO;
92 }
93 }
94 for(int i = 0; i <= n; i++) {
95 for(int j = 1; j <= n; j++) {
96 // cal g[i][j]
97 for(int k = 0; k < i; k++) {
98 g[i][j] = (g[i][j] + f[k][j - 1] * inv2 % MO) % MO;
99 }
100 }
101 }
102
103 // printf("%lld \n", g[2][1]);
104
105 // solve
106 d[0] = -1;
107 for(int x = 1; x <= n; x++) {
108 // x is smaller one
109 DFS1(x, 0);
110 DFS2(x, x);
111 // puts("");
112 }
113 // printf("ans = %lld\n", ans);
114 printf("%lld\n", ans * qpow(n, MO - 2) % MO);
115 return 0;
116 }
AC代码
E