T1
分层图跑最短路。为了优化空间，用了隐式连边的方法。
T2
dp，主要的想法是合并排列。
T4
交换的个数是具有传递性的，所以可以找连通块的信息。又因为具有单调性，可以用二分去找。然后多重集排列即可，公式 \(\frac{n!}{\prod s_i!}\)。
T5
首先，对 \(a\) 和 \(b\) 都分别排序，求出 \(r_i\) 表示比 \(a_i\) 小的 \(b_j\) 个数。
然后，设 \(dp_{i,j}\) 表示前 \(i\) 颗糖，有 \(j\) 颗是大于对应的药，的方案数（只考虑比对应药大的糖的差异，不考虑其他的糖），则 \(dp_{0,0}=1,dp_{i,j}=dp_{i-1,j}+(r_i-j+1)dp_{i-1,j-1}\)，输出 \(dp_{n,k} 就过样例了\)。
令 \(f_i=(n-i)!dp_{n,i}\)，表示把不比药大的糖随便分配给药片，所以意义是至少有 \(j\) 颗是大于对应的药（考虑确定大于的糖的方案与其他不确定是否大于的糖的对应的药的差异）。
令 \(g_i\) 表示恰好有 \(i\) 颗糖大于对应的药的方案数，则 \(f_i=\sum_{j=i}^n C_j^ig_j\)（枚举大于等于 \(i\) 的 \(j\)，要在 \(g_j\) 中确定 \(i\) 个确定大于的），由容斥原理可以得到 \(g_i=\sum_{j=i}^n(-1)^{j-i}C_j^if_j\)。
证明：
\[\sum_{j=i}^n(-1)^{j-i}C_j^if_j =\sum_{j=i}^n(-1)^{j-i}C_j^i\sum_{k=j}^n C_k^jg_k =\sum_{j=i}^ng_i\sum_{k=i}^j (-1)^{k-i}C_j^kC_k^i =\sum_{j=i}^ng_i\sum_{k=i}^j (-1)^{k-i}C_j^iC_{j-i}^{k-i} =\sum_{j=i}^nC_j^ig_i\sum_{k=i}^j (-1)^{k-i}C_{j-i}^{k-i} =\sum_{j=i}^nC_j^ig_i\sum_{k=0}^{j-i} (-1)^{k}C_{j-i-k}^{k} = g_i \]上面差一个 \(\sum_{i=0}^n(-1)^iC_n^i=0 (k>0)\)。
以及另一种形式：若 \(f_i=\sum_{j=0}^iC_i^jg_j\)，则 \(g_i=\sum_{j=0}^i(-1)^{i-j}C_i^jg_j\)。
这道题启示计数通过算至多、至少、至多确定等方法间接算答案。
T3
kruskal 重构树上 dp，见题解。
一般来说，树上问题比图上问题更容易，所以把图上问题转化为树上问题是一种方向，常见的有最小生成树、kruskal 重构树、最短路树（CF1163F,安全路径）、边双缩点、点双缩点（P3225）。
标签：练习赛,sum,2023.6,ig,大于,iC,jg,dp,Mon From： https://www.cnblogs.com/recollect-the-past/p/17981261