Avito Code Challenge 2018

F. Round Marriage

题目传送门
显然的霍尔定理
利用前缀和处理一波最小区间即可

G. Magic multisets

题目传送门
拆分成区间+1和区间*2两种操作就是标准的双标记线段树了
可以证明拆分后的操作数最多为2q(因为q中的每个区间最多被合并一次)

H. K Paths

题目传送门
考虑树形dp
$f[u]$表示存在从$u$开始的一部分是所有路径的公共部分的方案数
然后就是简单的子树合并
难点在于如果公共部分的端点刚好是$u$的时候
如果另一个端点是$u$的祖先,分治$ntt$即可
如果在$u$的子树内,考虑dp,逆操作还原回去即可
逆操作复杂度小于$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
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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
const int mod = 998244353;
const int maxn = 1e5 + 5;
int add(int x, int y) {
if((x += y) >= mod) x -= mod;
return x;
}
int mul(int x, int y) {
LL z = 1LL * x * y;
return z - z / mod * mod;
}
int powt(int a, int b) {
int r = 1;
while(b) {
if(b & 1) r = mul(r, a);
a = mul(a, a);
b >>= 1;
}
return r;
}
int wn[20];
void GetWn() {
for(int i = 0; i < 20; i++) {
int t = 1 << i;
wn[i] = powt(3, (mod - 1) / t);
}
}
void NTT(int a[], int len, int t) {
for (int i = 0, j = 0; i < len; i++) {
if (i > j) swap(a[i], a[j]);
for (int l = len >> 1; (j ^= l) < l; l >>= 1);
}
int id = 0;
for(int h = 2; h <= len; h <<= 1) {
id++;
for(int j = 0; j < len; j += h) {
int w = 1;
for(int k = j; k < j + h / 2; ++k) {
int u = a[k];
int t = mul(w, a[k + h / 2]);
a[k] = add(u, t);
a[k + h / 2] = add(u, mod - t);
w = mul(w, wn[id]);
}
}
}
if(t == -1) {
for(int i = 1; i < len / 2; i++) swap(a[i], a[len - i]);
LL inv = powt(len, mod - 2);
for(int i = 0; i < len; i++) a[i] = mul(a[i], inv);
}
}
vector<int> g[maxn];
unordered_map<int, int> q;
int sz[maxn], f[maxn], n, k, ans;
int p[maxn], inv[maxn];
int a[maxn << 2], b[maxn << 2], c[maxn << 2], tot;
void solve(int l, int r) {
if(l == r) return;
int mid = (l + r) >> 1, m, i;
solve(l, mid);
solve(mid + 1, r);
for(m = 1; m <= r - l + 1; m <<= 1);
a[0] = b[0] = 1;
for(i = l; i <= mid; i++) a[i - l + 1] = c[i];
for(i -= l - 1; i < m; i++) a[i] = 0;
for(i = mid + 1; i <= r; i++) b[i - mid] = c[i];
for(i -= mid; i < m; i++) b[i] = 0;
NTT(a, m, 1);
NTT(b, m, 1);
for(i = 0;i < m; i++) a[i] = mul(a[i], b[i]);
NTT(a, m, -1);
for(i = 0;i <= r - l; i++) c[l + i] = a[i + 1];
}
void dfs(int u, int fa) {
sz[u] = 1;
for(auto v : g[u]) {
if(v == fa) continue;
dfs(v, u);
sz[u] += sz[v];
ans = add(ans, mul(f[u], f[v]));
f[u] = add(f[u], f[v]);
}
tot = 0;
for(auto v : g[u]) {
if(v == fa) c[tot++] = n - sz[u];
else c[tot++] = sz[v];
}
q.clear();
solve(0, tot - 1);
int d, res;
for(auto v : g[u]) {
if(v == fa) d = n - sz[u];
else d = sz[v];
if(q.find(d) == q.end()) {
a[0] = res = 1;
for(int i = 0;i < tot; i++) {
a[i + 1] = add(c[i], mod - mul(a[i], d));
if(i < k) res = add(res, mul(a[i + 1], mul(p[k], inv[k - i - 1])));
}
q[d] = res;
}
if(v == fa) f[u] = add(f[u], q[d]);
else ans = add(ans, mul(f[v], q[d]));
}
}
int main() {
#ifdef CX_TEST
freopen("E:\\program--GG\\test_in.txt", "r", stdin);
#endif
int i, u, v;
GetWn();
scanf("%d%d", &n, &k);
if(k == 1) return printf("%lld\n", 1LL * n * (n - 1) / 2 % mod), 0;
if(n == 1) return puts("0"), 0;
for(i = p[0] = 1; i < maxn; i++) p[i] = mul(p[i - 1], i);
inv[maxn - 1] = powt(p[maxn - 1], mod - 2);
for(i = maxn - 1; i > 0; i--) inv[i - 1] = mul(inv[i], i);
for(i = 1; i < n; i++) {
scanf("%d%d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, 0);
printf("%d\n", ans);
return 0;
}