OI problems

给定 $n$ 个长度为 $m$ 的串 $T_i$，对于一个串 $S$，每次在 $S$ 后面以 $p_i$ 概率加一个字符 $i$，包含一个 $T_j$ 则停止，给出一个串 $R$，求所有 $S=R[1,i]$ 时，停止的期望长度。

$n\le 100,nm\le 10000$ 。

PGF 倒闭了！！！

给定 $m$ 个二元组 $(a_i,b_i)$，构造一张 $m-1$ 条边的图，使得 $\sum dis(a_i,b_i)$ 最小，并求方案数对 $10^9+7$ 取模。

$n\le 2000,nm\le 2\times 10^7$ 。

对自然数 $x$ 定义 $U(x)=\{0,1,2,...,x\}$，给定正整数 $n,m$，求：

$$\sum_{r=0}^{n-1}(\sum_{S\subseteq U(nm-1)}[(\sum_{x\in S}x)\bmod n=r])^2$$

答案对 $998244353$ 取模，$n,m\le 10^{12}$ 。

多组数据，$T\le 50$ 。

给定一棵 $n$ 个点的树，第 $i$ 个点上有一个体积为 $a_i$，价值 $b_i$ 的物品，每个点为黑色或者白色。

在树上选择若干个点，要求每个被选的点的最近的被选的祖先要和他异色，并且体积和 $\le W$，求最大价值和。

需要对原树的每棵子树求出答案。

$n\le 200,W\le 5\times 10^4$ 。

数轴上有三个相同的点 $A,B,C$，你需要通过恰好 $K$ 次操作把点移动到 $D,E,F$，求方案数。

每次操作，选择两个点，将一个点移动到另一个点轴对称的位置，但是只能越过一个点，并且不能出现两个点位置相同。

$A,B,C,D,E,F\le 10^{18},K\le 10^6$ 。

两人博弈，随机一棵 $n$ 个点的树，每条边边权在 $[0,m]$ 里随机。

现在随机一个点放一枚棋子，两人轮流移动，每次只能选边权 $>0$ 的边移动，然后边权 $-1$ 。

求先手必胜概率，答案对质数 $p$ 取模。

$n\le 10^6$​ 。

给定 $n,x$，对于每个 $1\le y\le n$，求出所有满足 $p_x=y$ 的排列 $p$ 有多少种本质不同的笛卡尔树，答案对 $998244353$ 取模。

$n,x\le 5\times 10^5$ 。

有一棵大小为 $n$ 的树，把 $k$ 个点染成黑色，一条边的权值为把它断掉后两个联通块黑点数量之差，求权值之和最小值。

$n,k\le 5\times 10^5$ 。

有一棵大小为 $n$ ，边带权的树，再定义一个大小为 $n$ 的完全图，其中两点 $(i,j)$ 的边权为树上距离，求对于每个 $k\le n/2$，大小为 $k$ 的匹配的最大权值。

$n\le 10^6$ 。

GF 加训！

已知 $n,x,y$​，求：

$$\sum_{i=1}^n \gcd(i,n)^x\text{lcm}(i,n)^y$$

$n\le 10^{18},x,y\le 2000$