20260806 学习日记

上午：补题

通过题目：（大概是视角转换类dp）
蓝CF321E
蓝P1758
蓝P4492
青P1450
蓝P5664
蓝P2619

下午：学习树上dp 组合dp 容斥dp

组合数小知识：

1. \(x^m=\sum_{p=0}^{m}S(m,p)\binom{x}{p}p!\)
   其中S(m,p)是斯特林数

---

树上dp

1. 一棵树，树上选k个点，不能选相邻点，最大化点权和
   \(n \leq 10^5, k \leq 100\)
   做法待补 \(\color{red}{待补}\)

2. 黑P4827
   思路：
   \(ans_i=\sum_{j=1}^{n} dist(i,j)^k\)
   \(= \sum_{j=1}^{n} \sum_{p=0}^{k} S(k,p) \binom{dist(i,j)}{p}p!\)
   \(= \sum_{j=1}^{n} \sum_{p=0}^{k} S(k,p)(\binom{dist(i,j)-1}{p} + \binom{dist(i,j)-1}{p-1})p!\)
   \(= \sum_{p=0}^{k} S(k,p) \cdot p! \cdot \sum_{j=1}^{n} \left[ \binom{dist(i,j)-1}{p} + \binom{dist(i,j)-1}{p-1} \right]\)
   考虑换根dp，设 \(f_{i,p}\) 表示以 \(i\) 号节点为根时， \(\binom{dist(i,j)}{p}\) 的值，则很容易推出 \(f_{i,p} = \sum(f_{son,p}+f_{son,p-1})\)
   这道题就做完了

---

容斥原理

1. LOJ575
   给出一个由大于小于号构成的序列，长度为 \(n-1\)，问有多少个 \(n\) 的全排列满足这个序列的要求
   \(n \leq 5000\)
   例：\(1<4>2<3\)
   思路：[<><>]=[<o<o]-[<<<o]-[<o<<]+[<<<<]

2. 紫AT_arc101_c
   思路：全覆盖=不做限制-没有全覆盖，即连通块

3. 蓝P5664
   思路：烹饪方法互不相同很好做
   没有>k/2 = 不做限制 - 有>k/2，且只能有一个食材>k/2
   枚举哪一列>k/2，dp即可

---

高阶状压dp

1. 紫P3343
   题意：每条边的边权在 \([0,1]\) 中等概率取，求图的最小生成树中最大边权的期望值
   提示：\(n \leq 10\)，对于 \(p\) 个 \([0,1]\) 的随机变量，第k大的期望是 \(\frac{k}{p+1}\)
   思路：即求解：在图中选 \(a\) 条边，满足它们是连通的；再在 \(a\) 条边中选一条边 \(E\)，满足删除 \(E\) 后这个图就不连通；
   枚举点集 \(S,T\)，无疑是可以状压的，然后枚举它们之中的边

2. 紫P2150
   思路：对于满足 \(p>\sqrt{n}\) 的质因子 \(p\)，每个数最多只能拥有一个

3. 紫P5369
   思路：考虑最后选到的下标 \(p\) 的性质，即 \(s[p,i] \leq 0, 0 \leq s[i,p]\)。
   思路待补 \(\color{red}{待补}\)

4. 紫P3959
   思路(Naive)：枚举根节点，然后枚举第 \(i\) 层是哪些节点……状态 \(f[S][T][k]\)，复杂度 \(O(爆炸)=O(2^{2n}*n)\)(貌似)
   思路(Naive but more nb): 我们直接抛弃一维，因为如果点 \(P\) 要连到点 \(Q\)，不可能连到再上一层，因为连上一层比连更以前的层更优……复杂度 \(O(3^n*n+2^n*n*m)\)

---

晚上：补题

通过题目：
黑P4827 (黑题首A祭)
紫P2150