毛姐姐的ppt做的真好看///
动态规划
由于ppt里真的很详细了，建议看ppt理解
这里做一些小批注
-
Gcd Counting
-
You are given a tree
证明：f中不同的取值个数是(sqrt{n})级别的
当(k leq sqrt{n})时 必然只有不多于(sqrt{n})种取值
当(k geq sqrt{n})时 (ans leq n / k， n / k leq sqrt{n}) 所以也不多于(sqrt{n})种取值
小套路：对于单调的答案 边界上二分
(O(n sqrt{n} log n))
-
Vladislav and a Great Legend
(x^k = sum_{i = 0}^{x} binom{x}{i} i! S(k, i))
(S(k, i))是第二类斯特林数
表示将k个不同元素拆分成i个集合（k个不同的球放进i个相同的筐）的方案数
S[0][0] = 1;
for(int i = 1; i <= k; ++i)
for(int j = 1; j <= i; ++j){
S[i][j] = (S[i - 1][j - 1] + (ll)(S[i - 1][j] * j % P) % P);
}
关于这个式子的解释。。
(x^k)可以看作k个不同的筐里 每个筐放1~x个相同的小球
右边(sum_{i = 1}^{x})是枚举有多少个本质不同的筐（本质不同就是里面放的小球数不同
我们让筐拥有姓名 就乘上( binom{x}{i})，表示选择这i个本质不同的筐各有多少个小球，但球数相同的筐仍然是一样的，而且我们并不知道每种球数的筐有几个
(i!S(k, i))是k个姓名，被放进i个集合，并把集合排序分发给筐，于是筐和球过上了幸福的生活
用这个也可以导出斯特林数通项公式
(ans = sum_{x}sum_{i = 0}^{k} binom{f(X)}{i}i!S(k, i))
(sum_{i = 0}^{k} i!S(k, i) sum_{x} binom{f(X)}{i})
背包size和k取一个min 可以分析出这样的背包复杂度为(O(nk))
-
Uniformly Branched Trees
有t棵子树大小等于k
(f[i][j][k] = f[i - t * k][j - t][k - 1] binom{f[k][d - 1][k - 1] + t - 1}{t})
解释一下这个式子
(f[i][j][k])表示节点数为i，共有j棵⼦树，有t棵子树的大小等于k
(f[i - t * k][j - t][k - 1])很显然啦
(f[k][d - 1][k - 1])是因为要求中间节点度数为d 而且它每棵子树多大并不限制
确定了前d - 1个子树之后 为了保证总点数为k 最后一棵子树的点数也确定了
( binom{f[k][d - 1][k - 1] + t - 1}{t})表示在X种⽅案中不分顺序地选取t种，可重复的⽅案数
最后的答案
(ans = f[n][d][frac{n}{2}] - binom{f[frac{n}{2}][d - 1][frac{n}{2} - 1] + 1}{2})
注意右上角的加一是因为左右两部分可以相同形态，所以需要增加一个选项
(O(n^2d^2))
递推式分析
(f[i] = sum f[j - 1] binom{i - 1}{i - j} (i - j)!)
枚举最大值出现在j的位置 满足前j-1个数允许最大值出现
( binom{i - 1}{i - j} (i - j)!)表示第j位（即最大值）之后填充的是哪几个数字以及它们的排列
-
Easy Problem
子序列做法：(f[i](0 leq i leq 3))表示现在最多有i个字母的最小代价
若s[i]为第j个字母 那么(f[j] = min(f[j - 1], f[j] + a[i]))
子串做法：单词内贪心一下，每个hard取四个字母中最小代价作为代价
- Kuro and Topological Parity
link
- Hero Meet Devil
感觉所谓dp套dp
就是把一些影响统计并且随着转移改变的量写进状态里
- XHXJ’s LIS
与上一题很类似 因为LCS非常短 用状态压缩模拟一般的求LCS过程