2017 Multi-University Training Contest 3 solutions

8/11 被zzq吊打了3h的罚时

先写自己做的几题, 其他再说

02

03

注意到 $K$ 很小,所以拿个链表串起来就行了, 每次暴力跳$K$ 步, 这样复杂度就是 $O(nlog n + nK)$
//code by liouzhou_101

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
68
69
70
71
72
73
74
75
76
77
const int MAXN = 500010;
const int MOD = 1000000007;
ll (ll a,ll b,ll p)
{
if (b==0) return 1;
ll t=power(a,b>>1,p);
t=t*t%p;
if (b&1) t=t*a%p;
return t;
}
int n, k;
pii a[MAXN];
int pre[MAXN], nxt[MAXN];
int buf[MAXN];
int *u = buf+250000;
int main()
{
int T;
scanf("%d", &T);
while (T --)
{
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; ++ i)
{
int x;
scanf("%d", &x);
a[i] = pii(x, i);
}
for (int i = 0; i <= n+1; ++ i)
{
pre[i] = 0;
nxt[i] = n+1;
}
sort(a+1, a+n+1, greater<pii>());
set<int> H;
ll ans = 0;
for (int i = 1; i <= n; ++ i)
{
auto it = H.insert(a[i].Y).X;
auto itx = it, ity = it;
if (itx != H.begin())
u[-1] = *-- itx;
else
u[-1] = 0;
++ ity;
if (ity != H.end())
u[1] = *ity;
else
u[1] = n+1;
pre[a[i].Y] = u[-1];
nxt[a[i].Y] = u[1];
nxt[u[-1]] = a[i].Y;
pre[u[1]] = a[i].Y;
u[0] = *it;
for (int d = 1; d <= k; ++ d)
{
u[-d] = pre[u[-d+1]];
}
for (int d = 1; d <= k; ++ d)
{
u[d] = nxt[u[d-1]];
}
for (int d = 0; d < k; ++ d)
{
int L = -d, R = k-1-d;
if (u[L] == 0 || u[R] == n+1) continue;
ans += (ll)(u[L]-u[L-1])*(u[R+1]-u[R])*a[i].X;
}
}
printf("%I64dn", ans);
}
return 0;
}

04

前缀拿个 $30n$ 的数组记下, 后缀拿个插了 $n$ 个数的trie, 每次删除一个来维护。 这样就是 $O(30n)$
// code by liouzhou_101

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
const int MAXN = 500010;
const int MAXK = 30;
int node_cnt;
struct node
{
node *son[2];
int tot;
}tree[MAXN*MAXK*2];
node *nil = tree;
node *new_node()
{
node *it = &tree[++ node_cnt];
it->son[0] = it->son[1] = nil;
it->tot = 0;
return it;
}
node *root[MAXN];
node *add(node *r, int x)
{
node *it = new_node();
*it = *r;
it->tot ++;
node *ret = it;
for (int k = MAXK-1; k >= 0; -- k)
{
int s = x>>k&1;
it->son[s] = new_node();
*it->son[s] = *r->son[s];
it = it->son[s];
r = r->son[s];
it->tot ++;
}
return ret;
}
int n;
int a[MAXN];
ll f[MAXK][2];
void del(int i)
{
node *r = root[i-1];
for (int k = MAXK-1; k >= 0; -- k)
{
int s = a[i]>>k&1;
f[k][s^1] -= r->son[s^1]->tot;
r = r->son[s];
}
}
int add(int i)
{
node *r = root[n], *rr = root[i];
for (int k = MAXK-1; k >= 0; -- k)
{
int s = a[i]>>k&1;
f[k][s] += r->son[s^1]->tot-rr->son[s^1]->tot;
r = r->son[s];
rr = rr->son[s];
}
}
int main()
{
nil->son[0] = nil->son[1] = nil;
nil->tot = 0;
int T;
scanf("%d", &T);
while (T --)
{
node_cnt = 0;
root[0] = new_node();
scanf("%d", &n);
for (int i = 1; i <= n; ++ i)
{
scanf("%d", &a[i]);
root[i] = add(root[i-1], a[i]);
}
for (int k = 0; k < MAXK; ++ k)
f[k][0] = f[k][1] = 0;
ll ans = 0;
for (int i = 1; i <= n; ++ i)
{
del(i);
for (int k = MAXK-1; k >= 0; -- k)
{
ans += f[k][a[i]>>k&1];
}
add(i);
}
printf("%I64dn", ans);
}
return 0;
}

05

考虑一个点集的斯坦纳树大小,类似于 $1 to x$ 的链的并

那么一个子树 $x$ ,如果字数内有 $a$ 个分在不同集合内的点, $v(fa_x, x)$ 就会被记 $a$ 次, 枚举每条边贪心最大化贡献即可

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
const int MaxN = 1001234;
int n, K, siz[MaxN], fv[MaxN];
struct edge{
int to, nxt, c;
}e[MaxN << 1]; int cnt, lst[MaxN];
void ins(int a, int b, int c){
e[++cnt] = (edge){b, lst[a], c}; lst[a] = cnt;
}
void lnk(int a, int b, int c){
ins(a, b, c);
ins(b, a, c);
}
void dfs(int x, int fa = 0){
siz[x] = 1;
for(int i = lst[x], b; b = e[i].to, i; i = e[i].nxt){
if(b == fa) continue;
dfs(b, x);
fv[b] = e[i].c;
siz[x] += siz[b];
}
}
int main() {
int i;
int size = 20 << 20;
char *p = (char *)malloc(size) + size;
__asm__("movq %0, %%rspn" :: "r"(p));
while(scanf("%d", &n) != EOF){
K = inp();
for(i = 1; i < n; i++){
int u = inp(), v = inp(), w = inp();
lnk(u, v, w);
}
dfs(1);
LL ans = 0;
for(i = 2; i <= n; i++)
ans += (LL) min(siz[i], K) * fv[i];
printf("%I64dn", ans);
for(i = 1; i <= n; i++) lst[i] = 0;
cnt = 0;
}
exit(0);
return 0;
}

06

观察发现就是要求 $f(x - sum_{i = 1} ^ {m} a_i )$

那么设 $o = sum_{i = 1} ^ {m} a_i$,有

观察发现是个卷积的形式, 套个板子即可

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
const int M = 23, P = ((7 * 17) << M) + 1, G = 3;
const int MaxN = (1 << 20) + 10;
int N = 1 << 19;
inline int add(int a, int b) {
return (a + b) % P;
}
inline int sub(int a, int b) {
return (a - b + P) % P;
}
inline int mul(int a, int b) {
return (LL)a * (LL)b % P;
}
inline int exp(int a, int b) {
int ans = 1;
for (; b; b >>= 1) {
if (b & 1) ans = mul(ans, a);
a = mul(a, a);
}
return ans;
}
inline int inv(int x) {
return exp(x, P - 2);
}
int eps[MaxN], ieps[MaxN], temp[5][MaxN];
inline void init() {
int g = exp(G, (P - 1) / N), ig = inv(g);
eps[0] = ieps[0] = 1;
for (int i = 1; i < N; i++) eps[i] = mul(eps[i - 1], ig), ieps[i] = mul(ieps[i - 1], g);
}
inline void trans(int n, int x[], int w[]) {
for (int i = 0, j = 0; i != n; i++) {
if (i < j) std::swap(x[i], x[j]);
for (int l = n >> 1; (j ^= l) < l; l >>= 1);
}
for (int i = 2; i <= n; i <<= 1) {
int l = i >> 1, d = N / i;
for (int j = 0; j != n; j += i)
for (int k = 0; k != l; k++) {
int t = mul(x[j + k + l], w[d * k]);
x[j + k + l] = sub(x[j + k], t);
x[j + k] = add(x[j + k], t);
}
}
}
inline void dft(int n, int x[]) {
trans(n, x, eps);
}
inline void idft(int n, int x[]) {
trans(n, x, ieps);
for (int i = 0, in = inv(n); i < n; i++) x[i] = mul(x[i], in);
}
int fac[MaxN], rfac[MaxN];
int f[MaxN], n, m, of, a[MaxN], b[MaxN];
int u[MaxN], v[MaxN];
int main() {
int i, L;
init();
for(fac[0] = 1, i = 1; i < MaxN; i++) fac[i] = mul(fac[i - 1], i);
for(rfac[MaxN - 1] = exp(fac[MaxN - 1], P - 2), i = MaxN - 1; i; i--)
rfac[i - 1] = mul(rfac[i], i);
while(~ scanf("%d", &n)){
for(i = 0; i <= n; i++) f[i] = inp();
m = inp(); of = 0;
for(i = 1; i <= m; i++) a[i] = inp(), of = add(of, a[i]);
for(a[0] = 1, i = 1; i <= n; i++) a[i] = mul(a[i - 1], P - of);
for(i = 0; i <= n; i++) u[n - i] = mul(f[i], fac[i]);
for(i = 0; i <= n; i++) v[i] = mul(a[i], rfac[i]);
for(L = 1; L <= (n + n + 1); L <<= 1);
dft(L, u); dft(L, v);
for(i = 0; i < L; i++) u[i] = mul(u[i], v[i]);
idft(L, u);
for(i = 0; i <= n; i++)
printf("%d ", mul(u[n - i], rfac[i]));
puts("");
for(i = 0; i < L; i++) u[i] = v[i] = 0;
}
return 0;
}

07

08

求 $sum_{i = 1}^{n^k}{mu^2(i) times lfloor sqrt{frac{n^k}{i}} rfloor}$

注意到这个式子好像是唬人的,注意到对于一个数 $x = a^2b$, 其中 $mu(b) neq 0$,这个分解是唯一的

那么这个式子就相当于枚举了那个 $b$, 统计了 $n^k$ 中所有 $b$ 的倍数,这样每个数会被记录恰好一次, 答案就是 $n^k$

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
const int P = 1000000007;
inline LL mul(LL a, LL b) {
return (LL)a * b % P;
}
inline int exp(LL a, LL b) {
LL ans = 1;
a %= P;
for (; b; b >>= 1) {
if (b & 1) ans = mul(ans, a);
a = mul(a, a);
}
return ans;
}
int main() {
int i = 0;
LL n, K;
while(scanf("%I64d%I64d", &n, &K) != EOF)
printf("Case #%d: %dn", ++i, exp(n, K));
return 0;
}

09

题意可以明显的转化成有向图欧拉回路计数(起点限制为1)

由于Best theorem, 我们用原图的邻接矩阵 $D$ 减去出度矩阵 $A$, 记为 $G$, 记 $G$ 去掉第 $i$ 行第 $i$ 列之后的行列式为 $t(G, i)$, 这个值实际上是有向图的内向树个数

然后答案就是$t(G, i) times mathrm{deg}(1) times prod_{i = 2} ^ {n} (mathrm{deg}(i) - 1)!$

然后你发现错了

因为题目的特别要求, 你还要乘上 $prod_{i = 1} ^ {n}prod_{i = 1} ^ {n} mathrm{D}(i, j)!^{-1}$

阶乘预处理 tm 要预处理到 $O(n ^ 2)$

还要判 -1 。。。

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
const int MaxN = 555, MaxM = 555;
const int P = 998244353;
int n, m, d[MaxN][MaxN], fac[MaxN * MaxN], r[MaxN];
inline int add(int a, int b) {
return (a + b) % P;
}
inline int sub(int a, int b) {
return (a - b + P) % P;
}
inline int mul(int a, int b) {
return (LL)a * b % P;
}
inline int exp(int a, int b) {
int ans = 1;
for (; b; b >>= 1) {
if (b & 1) ans = mul(ans, a);
a = mul(a, a);
}
return ans;
}
int g[MaxN][MaxN];
int gauss(int N){
int i, j, k, l, o;
for(l = j = 1; j <= N; j++){
for(k = j; k <= N; k++)
if(g[j][k]) break;
if(k == N + 1) return 0;
if(k > j)
for(l *= -1, o = j; o <= N; o++)
swap(g[j][o], g[k][o]);
l = mul(l, g[j][j]);
o = exp(g[j][j], P - 2);
for(k = j; k <= N; k++)
g[j][k] = mul(g[j][k], o);
for(k = j + 1; k <= N; k++)
if(g[k][j])
for(o = N;o >= j; o--)
g[k][o] = sub(g[k][o], mul(g[k][j], g[j][o]));
}
return l < 0 ? l + P : l;
}
int f[MaxN];
int r2[MaxN];
int find(int x){
return f[x] == x ? x : f[x] = find(f[x]);
}
int main() {
int i, j, cas = 0;
for(fac[0] = 1, i = 1; i < MaxN * MaxN; i++) fac[i] = mul(fac[i - 1], i);
while(scanf("%d", &n) != EOF){
for(i = 1; i <= n; i++) f[i] = i;
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
d[i][j] = inp();
for(i = 1; i <= n; i++) r[i] = 0, r2[i] = 0;
int det = 1;
for(i = 1; i <= n; i++) for(j = 1; j <= n; j++) g[i][j] = 0;
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++){
if(d[i][j]) f[find(i)] = find(j);
g[j][j] = add(g[j][j], d[i][j]);
g[i][j] = sub(g[i][j], d[i][j]);
det = mul(det, exp(fac[d[i][j]], P - 2));
r[i] += d[i][j]; r2[j] += d[i][j];
}
det = mul(det, gauss(n - 1));
for(i = 1; i <= n; i++)
det = mul(det, fac[r2[i] - 1 + (i == 1)]);
for(i = 1; i <= n; i++) if(find(i) != find(1)) det = 0;
for(i = 1; i <= n; i++) if(r[i] != r2[i]) det = 0;
printf("Case #%d: %dn", ++cas, det);
}
}

10

考虑到设 $f(i, j)$ 表示前 $j$ 个分成 $i$ 段的最小代价,那么 $f(i, j) = min{f(i - 1, k) + mathrm{dep}(mathrm{lca}(p_{k + 1}ldots p_j))}$

注意到设$d(l, r) = mathrm{dep}(mathrm{lca}(p_l ldots p_r))$, 必然满足 $d(l, r + 1) - d(l, r) ge d(l + 1, r + 1) - d(l + 1, r)$, 想象添加点 $p_r$ 的时候, 额外多出的点 $p_l$ 会使得减量不变小, 二分 + 倍增维护区间lca就可以在 $O(nklog 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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
const int MaxN = 601234, MaxL = 20;
int n, K, P[MaxN];
struct edge{
int to, nxt;
}e[MaxN << 1]; int cnt, lst[MaxN];
void ins(int a, int b){
e[++cnt] = (edge){b, lst[a]}; lst[a] = cnt;
}
void lnk(int a, int b){
ins(a, b);
ins(b, a);
}
int dep[MaxN], lg[MaxN], dfn[MaxN], dn, eu[MaxN], en, in[MaxN];
void dfs(int x, int fa){
dfn[x] = ++dn; eu[++en] = x; in[x] = en;
for(int i = lst[x], b; b = e[i].to, i; i = e[i].nxt){
if(b == fa) continue;
dep[b] = dep[x] + 1;
dfs(b, x);
eu[++en] = x;
}
}
int a[MaxN][MaxL], c[MaxN][MaxL];
int LCA(int x, int y){
x = in[x]; y = in[y];
if(x > y) swap(x, y);
int o = lg[y - x + 1];
int l = c[x][o], r = c[y - (1 << o) + 1][o];
return dep[l] < dep[r] ? l : r;
}
int lca(int x, int y){
if(x > y) return 0;
int o = lg[y - x + 1];
int l = a[x][o], r = a[y - (1 << o) + 1][o];
return dep[LCA(l, r)];
}
int f[MaxN], g[MaxN];
int find(int x, int y){
int l, r, z, o;
for(l = y, r = n + 1; l < r; o ? l = z + 1 : r = z){
z = l + r >> 1;
o = g[x] + lca(x + 1, z) < g[y] + lca(y + 1, z);
}
return l;
}
int qh, qt, pt[MaxN], q[MaxN];
int main() {
int i, j;
for(lg[1] = 0, i = 2; i < MaxN; i++) lg[i] = lg[i >> 1] + 1;
while(~scanf("%d", &n)){
K = inp();
for(i = 1; i <= n; i++) P[i] = inp();
for(i = 1; i < n; i++) {
int u = inp(), v = inp();
lnk(u, v);
}
dep[1] = 1; en = dn = 0;
dfs(1, 0);
for(i = 1; i <= en; i++) c[i][0] = eu[i];
for(j = 1; j <= lg[en]; j++)
for(i = 1; i + (1 << j) - 1 <= en; i++){
int l = c[i][j - 1], r = c[i + (1 << j - 1)][j - 1];
c[i][j] = dep[l] < dep[r] ? l : r;
}
for(i = 1; i <= n; i++) a[i][0] = P[i];
for(j = 1; j <= lg[n]; j++)
for(i = 1; i + (1 << j) - 1 <= n; i++){
int l = a[i][j - 1], r = a[i + (1 << j - 1)][j - 1];
a[i][j] = LCA(l, r);
}
for(i = 1; i <= n; i++) f[i] = 1e9;
for(f[0] = 0, j = 1; j <= K; j++){
for(i = 0; i <= n; i++)
g[i] = f[i], f[i] = 1e9;
qh = 1, qt = 0;
for(i = 0; i <= n; i++){
for(; qh < qt && pt[qh + 1] <= i; qh++);
if(qh <= qt) f[i] = g[q[qh]] + lca(q[qh] + 1, i);
for(; qh < qt && pt[qt] >= find(q[qt], i); --qt);
q[++qt] = i;
if(qh < qt) pt[qt] = find(q[qt - 1], i);
}
}
printf("%dn", f[n]);
for(i = 1; i <= n; i++) lst[i] = 0;
cnt = 0;
}
return 0;
}

11

签到题