给定字符串长度n，求敲好出现k个“bit”的字符串个数。
反演或者容斥推导公式，推到公式后直接ntt优化即可。
一个道具需要升级，成功升级的概率为 p i p_i pi,升级失败并且下降 j ( 1 ≤ j ≤ i ) j (1\leq j \leq i) j(1≤j≤i)级的概率是 ( 1 − p i ) w j ∑ k = 1 i w k (1-p_i)\frac{w_j}{\sum_{k=1}^{i} w_k} (1−pi)∑k=1iwkwj,求升级到n级的期望。
首先根据期望推导公式，得到 E i + 1 = E i − c i − ( 1 − p i ) ∑ j = 1 i w j ⋅ ( ∑ j = 1 i w j ⋅ E i − j ) p i E_{i+1}=\frac{E_{i}-c_{i}-\frac{\left(1-p_{i}\right)}{\sum_{j=1}^{i} w_{j}} \cdot\left(\sum_{j=1}^{i} w_{j} \cdot E_{i-j}\right)}{p_{i}} Ei+1=piEi−ci−∑j=1iwj(1−pi)⋅(∑j=1iwj⋅Ei−j), 又由于不知道 E 0 E_0 E0,所以考虑使用 E i = a i ∗ E 0 + b i E_i = a_i*E_0+b_i Ei=ai∗E0+bi的形式替换原来的 E i E_i Ei，这样就能得到关于 a i a_i ai和 b i b_i bi的一个正确的表达式，而且知道初始值为 a 0 = 1 , b 0 = 1 a_0 = 1, b_0 = 1 a0=1,b0=1, 这个时候就能使用分治ntt进行优化了。
树上期望和区间组合数学，一道期望和组合题，角度：边。无向边变成有向边的贡献
给定一个树，随机将k条边变成指向1的有向边，求从起点s到1的走过的边数期望，在每个节点走向的下一条边的概率相等。
一个常用结论：每个结点走到父节点的期望值等于该子树的大小。
而将一条无向边变成有向边对于这条有向边连接的子树而言没有任何影响，对于所连接的父亲而言，相当于删除了改边。
从边的角度考虑处理每条边对期望的贡献，首先考虑这条边对所有必过点的贡献，发现贡献都是该子树大小乘以2。而每个边贡献的概率只与其到必过点的距离有关，所以可以使用深度来对距离进行统计，使用区间加减的思路优化时间复杂度。