传送门：Hello 2019 G. Vladislav and a Great Legend

题面

给一棵有根树 $T=(V,E)$，$X$ 是 $V$ 的非空子集，记 $f(X)$ 表示 $T$ 中使得点集 $X$ 联通的最小联通子图中的边数，求

$$
\sum_{X\subseteq V,X \neq \varnothing} (f(X))^k
$$

其中，$3 \le |V| \le 10^5,1\le k \le 200$ 。

分析

显然，$k=1$ 直接扫一遍算贡献即可。

考虑 $k>1$ 的情况，由第二类斯特林数展开

$$
(f(X))^k=\sum_{i=0}^{k}S(k,i)i!{f(X) \choose i}
$$

前面一部分可以预处理，也就是要求对于 $i (0\le i \le k)​$

$$
\sum_{X\subseteq V,X \neq \varnothing} {f(X) \choose i}
$$

设 $E’ \subseteq E$ 且 $|E’|=i$，$E_X$ 为 $f(X)$ 对应联通块的边集，上式可以写成

$$
\sum_{X\subseteq V,X \neq \varnothing} \sum_{e_j \in E’,1\le j \le i} [e_1,e_2,\dots,e_i \in E_X]
$$

于是，交换求和顺序

$$
\sum_{e_j \in E’,1\le j \le i} \sum_{X\subseteq V,X \neq \varnothing} [e_1,e_2,\dots,e_i \in E_X]
$$

上式含义是枚举边集 $E$ 的大小为 $i$ 的子集 $E’$，计算 $E’$ 出现在多少个点集 $V$ 的非空子集 $X$ 对应的联通块内。

考虑 $dp(i,j)$ 表示以 $i$ 为根的子树内大小为 $j$ 的边集，在子树内对上式的贡献。

设当前计算的根为 $u$，有三种情况：

1. $u​$ 到子树的边单独构成边集。
2. $u$ 到子树的边与这棵子树的边集合并。
3. $u$ 的子树的边集之间合并，子树的边集包含前两种情况。

对于以 $v$ 为根的子树，更新 $v$ 的 $dp$ 状态，情况一就是 $dp(v,1)+2^{size(v)}-1$，而情况二是用 $dp(v,i)$ 更新 $dp(u,i+1)$ 。得到每一个子树 $v$ 的 $dp$ 状态，做一个卷积即可得到根 $u$ 的 $dp$ 状态。

考虑卷积的过程，如果 $v_1$ 和 $v_2$ 合并，没有考虑到 $u$ 的其它子树对其的贡献。

为了解决这个问题，卷积过程中对于 $0$ 次项，设置其为 $2^{size(v)}$，这样没有参与合并的子树贡献就被计算进去了，注意这个部分的贡献不需要 $-1$。因为只要参与了合并，那么只有端点的子树才是必须非空，路径上的点都是可取可不取。

但是，状态转移的过程中，实际上已经对最终答案产生贡献，因为 $dp(i,j)$ 考虑的点集都是以 $i$ 为 $LCA$ 的。

对答案的贡献也有类似的三种情况。

情况一和情况二只需要考虑 $u$ 外的节点是否被取，更新答案即可。

情况三需要考虑合并后的边集对答案贡献，注意到卷积后实际上有一些是没有合并的，我们需要从 $u$ 的 $dp$ 状态中减去前两种情况，这有卷积结果就只剩下参与过合并的边集了。这部分边集同样是考虑 $u$ 外的节点是否选取。

于是，我们就得到了一个 $ans$ 数组表示大小为 $i$ 的边集 $E’$ 的贡献，使用第二类斯特林数即可得到最终答案。

时间复杂度 $O(nk^2)$。

最后参考树形依赖背包的优化原理，上面的卷积过程，实际上与子树大小有关，用类似的方法，我们最终得到时间复杂度为 $O(nk)​$ 的解法。

A Lunar New Year and Cross Counting

模拟一下（第一发写错了符号还能过样例是什么鬼？

B Lunar New Year and Food Ordering

C Lunar New Year and Number Division

把 $n$ 个划分成好多个集合（ $n$ 为偶数），记 $S_j$ 表示第 $j$ 个集合内数的和的平方，要求最小化 $\sum S_j$。

显然，排个序，最大的和最小的组成一组即可（容易证明）。

D Lunar New Year and a Wander

一个人在图上走，每次走到一个未经过的点，将其记录下来，求走遍这个图记录下的字典序最小的序列。

显然，直接贪心地 $dfs$ 是不行的。我们可以用优先队列做一个类似 $Prim$ 的过程，维护一下当前可以走到哪些没有走过的点。

E Lunar New Year and Red Envelopes

给一个长度为 $n$ 的时间轴，有 $k$ 个红包，每个红包可以在 $[s,t]$ 的时间内被领取，领取后获得价值 $w$，领取后直到 $d+1$ 时间才能继续领红包。

一个人贪心的领取红包，能领红包的话，就领价值最大且 $d$ 最大的那个。

你现在有 $m$ 次机会阻止他在某一个时间拿红包，你非常聪明，求这个人能获得的最小价值。

首先，线段树（ $set$ + 扫描线）预处理每个位置拿的红包 $a_i$。

考虑 $dp[i][j]$ 表示在前 $i$ 个时间内，被阻止了 $j$ 次获得的最小价值，转移方程

$$
dp[1][0]=0 \
dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]) \
dp[a[i].d + 1][j]=min(dp[a[i].d+1][j], dp[i][j]+a[i].w)
$$

题面

求 $n$ 个点 $m$ 条边的带标号图是某个 $n$ 个点的环的子图的个数。

分析

把几个情况特判掉：

1. $m>n$：图上已经有环。
2. $m=n$：图本身就是一个 $n$ 个点的环，答案为 ${n!\over2}$。
3. $m=0$：答案为 $1​$（底下的公式会挂在这个地方）。

题目等价于求将一个带标号的图分成 $n-m$ 条链的方案数（块内有序，块间无序）。

先给块间加一个有序条件，最后乘上 $n! \over (n-m)!​$ 即可去除掉块间的序，因此可以使用指数生成函数先算出块内块间有序的方案数。

考虑一条链的情况，只有一个点时，方案数为 $1$，有 $n$ 个点时 $(n \ge 2)$，方案数为 $n! \over 2$。因此得到对应的指数生成函数
$$
\begin{array}{}
f(x)&=&x+{2! \over 2}{x^2 \over 2!}+{3! \over 2}{x^3 \over 3!}+\dots \
&=&x+{1\over2}x^2+{1\over2}x^3+\dots \
&=&{x\over 2}+{1\over2}x(1+x+x^2+x^3+\dots) \
&=&{x\over 2}+{1\over2}{x \over 1-x}
\end{array}
$$
答案为
$$
\begin{array}{}
ans&=&{n! \over (n-m)!}[x^n]({x\over 2}+{1\over 2}{x \over 1-x})^{n-m} \
&=&{n! \over (n-m)!}[x^n]({x \over 2}(1+{1 \over 1-x}))^{n-m} \
&=&{n! \over (n-m)!2^{n-m}}[x^n]x^{n-m}(1+{1 \over 1-x})^{n-m} \
&=&{n! \over (n-m)!2^{n-m}}[x^m](1+{1 \over 1-x})^{n-m} \
&=&{n! \over (n-m)!2^{n-m}}[x^m]\sum_{i=0}^{n-m} {n-m \choose i} ({1 \over 1-x})^i \
&=&{n! \over (n-m)!2^{n-m}}[x^m]\sum_{i=0}^{n-m} {n-m \choose i} (1+x+x^2+\dots)^i \
&=&{n! \over (n-m)!2^{n-m}}\sum_{i=0}^{n-m} {n-m \choose i}{m+i-1 \choose m} \
\end{array}
$$

树上的每个节点均有各自的重量和价值，除了容量限制外，还要求选择一个节点时，其父节点也要被选择，求最大价值。

时间复杂度：$O(nm^2)$（其中 $n$ 为树的大小，$m$ 为容量限制）。

优化

对于枚举到的每个节点，记录一下其子树大小。

$dp$ 状态转移时，枚举的个数是当前这个子树大小，对应儿子节点的子树的大小，最后更新子树大小。

相当于每次转移都是从节点枚举过的子树，将没有枚举的儿子合并进来。这个过程对应于枚举以这个点为 $lca$ 的所有点对，总体上它枚举了树上所有点对。

时间复杂度：$O(n^2)$。

马神牛逼！（破音

马神牛逼！（破音

模板

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

ll qpow(ll x, ll n) {
    ll r = 1;
    while (n > 0) {
        if (n & 1) r = r * x % mod;
        x = x * x % mod; n >>= 1;
    }
    return r;
}
ll inv(ll x) { return qpow(x, mod - 2); }
ll rev[maxn << 2];
int init(int m) {
    int step = 0, n = 1;
    for (; n < m; n <<= 1) ++step;
    for (int i = 1; i < n; i++) 
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (step - 1));
    return n;  
}
void ntt(vector<ll>& a, int n, int op) {
    for (int i = 0; i < n; i++) if (i < rev[i]) swap(a[i], a[rev[i]]);
    for (int h = 2; h <= n; h <<= 1) {
        ll wn = qpow(3, (mod - 1) / h);
        if (op == -1) wn = inv(wn);
        for (int i = 0; i < n; i += h) {
            ll w = 1;
            for (int j = i; j < i + h / 2; j++) {
                ll u = a[j], t = a[j + h / 2] * w % mod;
                a[j] = (u + t) % mod;
                a[j + h / 2] = (u - t + mod) % mod;
                w = w * wn % mod;
            }
        }
    }
    if (op == -1) {
        ll rn = inv(n);
        for (int i = 0; i < n; i++) a[i] = a[i] * rn % mod;
    }
}

$div3$ 恢复信心失败。

A Two distinct points

B Divisors of Two Integers

给了一个多重集合，存放着两个正整数 $x$ 和 $y$ 的所有因子，让你恢复出这两个数字。

显然最大值是一个解，对其质因数分解，从多重集合中删除，得到剩下数字中的最大值为另外一个解。

C Nice Garland

给一个只包含字母 $RGB$ 的串，现在要求这个串 $s$ 满足
$$
\forall i, j \text{ 满足 } s_i=s_j,|i-j|\mod 3=0
$$
你可以修改一些位置使得上条件满足，求最小修改数和修改方案。

显然，这个串的前 $3$ 个位置只有 $6$ 种情况，后面部分一直重复这个前缀，枚举前缀即可。

D Diverse Garland

给一个只包含字母 $RGB$ 的串，现在要求这个串 $s$ 满足所有相邻位置字母不同。

你可以修改一些位置使得上条件满足，求最小修改数和修改方案。

考虑 $dp[i][3]$ 表示前 $i$ 个位置，最后一个为 $RGB$ 的最小修改数，跑一遍 $dp$，再倒着转移把方案构造出来。

菜鸡选手不会写倒着重构 $dp$。

E Array and Segments

给一个序列

$$
a_{1},a_{2},\cdot\cdot\cdot,a_{n}
$$

现在有 $q$ 次询问，每次将区间 $[l,r]$ 所有位置都 $-1$，现在你需要从询问中选择一些执行，使得序列极差最大，即最大化 $\max a_i - \min a_i$。

对于一类求极差的问题，可以转化为枚举一个，快速计算另外一个。

因此，我们枚举最大值的位置，将所有不包含这个位置的线段全部执行，询问整个区间的最小值，这部分线段树更新和查询即可。

但是此时复杂度为 $O(nm\log n)$。

优化一下，我们可以用类似于双指针的思想，枚举每一个位置时，更新一些询问和撤销一些询问，因此每个询问最多被更新 $2$ 次。

时间复杂度 $O((n+m)\log n)$。

菜鸡选手并不知道极差的套路。

F MST Unification

给一个无向带权连通图，现在你可以将某些边权 $+1$ ，求最小的修改次数使得修改后的最小生成树唯一，且最小生成树权值不增加。

已经求出一棵最小生成树，当且仅当一些非树边的权值等于其对应树上路径的最大边权时，可以将路径上的最大边断掉换成这个非树边。

所以问题转化为快速求得树上一条路径的最大边权，在树上建一棵主席树即可。

菜鸡选手没有思维，只会无脑拍数据结构。

$C$ 卡主席树内存，是不是有点毒瘤啊？不会卡内存，自闭了啊？