CF1943D2 Counting Is Fun (Hard Version)
充要条件是不存在 $1<i<n$ 使得 $a_i>a_{i-1}+a_{i+1}$。可以归纳证明。
对这个东西计数，暴力需要记两维，$f_{i,j,k}$ 表示 $i$ 上填了 $j$，$i-1$ 填了 $k$ 的方案数。
核心性质是，$i$ 和 $i-1$ 不能同时不合法。所以设 $f_{i,j}$ 表示 $i$ 上面填了 $j$ 并且 $[1,i-1]$ 都合法的方案数。转移是任意填一个数转移到 $f_{i+1}$。然后这样 $f_{i+1}$ 只是错误的把只有 $i$ 不合法的方案数加进去了，所以容斥一下，从 $f_{i-1,j}$ 也可以转移到 $f_{i+1}$。复杂度可以前缀和优化到 $\mathcal O(n^2)$。
CF1097G Vladislav and a Great Legend
唐氏题，设 $f_{i,j}$ 表示，$i$ 子树内选了一个连通块，连通块中选 $j$ 条边的方案数之和。转移是树形背包。
CF1392H ZS Shuffles Cards
很神秘的题。考虑期望抽到几张 joker，以及每抽到一张 joker 之前期望的抽到的有效牌数量。
答案就是期望轮数乘每轮期望抽牌数量（？）。证明：
\[\begin{aligned} &\sum E(\text{前 i-1 轮没有抽完})\times E(\text{第 i 轮期望抽牌数})\\ =&\sum E(\text{前 i-1 轮没有抽完})\times E(\text{一轮的期望抽牌数})\\ =&\sum E(\text{期望抽排轮数})\times E(\text{一轮的期望抽牌数})\\ \end{aligned}\]一轮期望抽牌数可以拆贡献，每张牌的贡献是 $\frac{1}{m+1}$，答案是 $\frac n {m+1}+1$。
期望轮数考虑 min-max 容斥，枚举 $i$，选 $i$ 张牌作为关键牌，则期望最小值就是 $\frac{i+m}{i}$。
CF1988F Heartbeat
挺牛的。前缀最大值和后缀最大值显然可以通过枚举最大值的位置分开算。
设 $f_{i,j,k}$ 表示长度为 $i$ 的序列，有 $j$ 个前缀最大值，$k$ 个上升值的方案数。经过尝试，可以不断插入最小值。如果在开头则 $j,k$ 都加一，如果在两个上升值中间则 $j,k$ 都不变，如果在两个非上升值之间则 $k$ 加一，如果在结尾则 $j,k$ 也都不变。转移是 $\mathcal O(1)$ 的。
然后可以处理出 $l_{i,j}$ 表示长度为 $i$，$j$ 个上升值，此时前缀最大值的数量已经知道，所以可以乘进系数里。还有 $r_{i,j}$ 表示长度为 $i$，$j$ 个上升值的后缀最大值数量贡献和。
这样 $l,r$ 的乘法就是一个二维卷积。拉格朗日插值暴力就是 $\mathcal O(n^3)$，但是常数比较烂。可以考虑枚举 $l_{i,j}$ 和最终上升值的个数 $x$，贡献到一个 $v_{i,x-j}$。然后就是 $v_{i,a}$ 和 $r_{j,a}$ 在第一维上的一个一维卷积，复杂度 $\mathcal O(n^3)$。
CF1707D Partial Virtual Trees
二项式反演把真子集的限制去掉。假设一开始所有点都点亮，然后一个一个的熄灭。限制就是如果 $i$ 有两个不同子树的点都点亮，那 $i$ 就必须不能熄灭。
设 $f_{i,j}$ 表示 $i$ 子树内，考虑了前 $j$ 个时刻，此时仍然有被点亮的点的方案数。
分类讨论，如果 $i$ 还点亮着，可以枚举每个子树什么时候熄灭：
\[f_{i,j}\leftarrow \prod_{(i,u)}\sum_{0\leq k\leq j} f_{u,k}\]转移前缀和优化。
如果 $i$ 熄灭了，枚举仅存的是哪个子树：
\[\begin{aligned} f_{i,j}&\leftarrow \sum_{(i,u)}f_{u,j}\prod_{(i,v),u\not=v}\sum_{0\leq k<j}f_{v,k}\\ s_{u,j}&=\sum_{k<j}f_{u,k} \end{aligned}\]预处理 $s$ 的前后缀积即可辅助转移。
CF1667E Centroid Probabilities
设 $f_i$ 表示子树大小大于等于 $\frac{n+1}2$ 的方案数。
\[\begin{aligned} f_i&=\sum_{j=\frac{n+1}{2}}^{n-i+1}(i-1)\binom{n-i}{j-1}(j-1)!(n-j-1)!\\ &=\sum_{j=\frac{n+1}{2}}^{n-i+1}(i-1)\frac{(n-i)!}{(n-i-j+1)!}(n-j-1)!\\ &=(i-1)(n-i)!(i-2)!\sum_{j=\frac{n+1}{2}}^{n-i+1}\frac{(n-j-1)!}{(n-i-j+1)(i-2)!}\\ &=(i-1)!(n-i)!\sum_{j=\frac{n+1}{2}}^{n-i+1}\binom{n-j-1}{i-2}\\ &=(i-1)!(n-i)!\binom{\frac{n-1}{2}}{i-2}\\ \end{aligned}\]CF708E Student’s Camp
$f_{i,l,r}$ 表示当前在第 $i$ 层，存在的墙是 $[l,r]$ 的概率，前缀和优化转移。
然后可以只对前缀和 DP，前缀和优化前缀和/tx/tx。
CF1842H Tenzing and Random Real Numbers
首先把所有数都减去 $\frac 1 2$，就变成了 $x_i+x_j\geq 0$ 或者 $x_i+x_j\leq 0$。
然后这个条件只和绝对值较大数的绝对值有关。把绝对值从大到小插入即可，最后除一个 $n!2^n$。
CF765E Byteland coins
先把 $m$ 进制转换，然后从高位向低位 DP，设 $f_{i,j}$ 表示考虑了高 $i$ 位，当前剩了 $j$，转移是转移到 $f_{i,k},k>j-b_i$，或者是到 $f_{i-1,j\times a_{i-1}+m_{i-1}}$。因为这样写不大好所以有点卡常。
CF1792F1 Graph Coloring (easy version)
图不可能都不联通。假设是红联通的，则蓝色形成了若干个连通块，连通块之间一定合法，只需要保证连通块内部合法。列出生成函数：
\[F(x)=x+e^{F(x)}-F(x)-1\]有复合逆
\[G(x)=2x+1-e^x\]套用拉格朗日反演：
\[[x^n]F(x)=\frac 1 n[x^{n-1}](\frac{x}{G(x)})^n\]暴力多项式快速幂即可。
CF506E Mr. Kitayuta’s Gift
时代变了。
设 $f_{i,l,r}$ 表示填了 $i$ 个字母，左边走到了第 $l$ 个，右边走到了第 $r$ 个，转移 $\mathcal O(1)$。
然后求出前 $\mathcal O(m)$ 项之后对答案序列上个 BM 就能直接把线性递推式爆出来，然后再用 bostan-mori 递推一下就行了。
CF1810G The Maximum Prefix
枚举第 $k$ 位算答案。设 $f_{i,j}$ 表示当前在 $i$，最大前缀和是 $j$，初值 $f_{k+1,0}=1$，然后转移是向前面加数，答案是 $\sum f_{1,j}h_j$。对上述过程转置即可在 $\mathcal O(n^2)$ 的时间复杂度内求出答案。