1124总结
1124总结
T1
有 \(n\) 个类似的条件，考虑容斥原理，条件可以被描述为 \(\forall i\in[1,n),a_i\nmid a_{i+1}\vee a_i=a_{i+1}\)。
容斥原理需要计算，钦定 \(x\) 个条件不成立，忽视其它条件时，合法的方案总数。
假设我们已经钦定好了 \(x\) 个条件，那么很容易计算出这个方案，将每一段连续的不合法的位置的方案数计算出来，其余位置不受限制即可，就是 \(m\)。
每一段连续不合法位置的贡献显然仅和长度有关，而长度又不超过 \(\log n\)，所以可以预处理一个 \(g[x]\) 表示连续 \(x\) 个连续不合法位置的贡献，注意到不合法位置开头的前一个位置也是需要考虑进去的，但它没有限制，所以连带算进去就行。
预处理的时候进行 \(dp\)，可以记录上一个位置的值。
计算出 \(g[x]\) 后，我们不需要死板的去考虑有 \(x\) 个位置不合法时，它们的分布是什么，如果这样考虑，那么每一个 \(x\) 都需要进行一次动态规划来计算答案并乘上容斥系数。
我们可以用一次动态规划完成整个统计过程。
设 \(dp[i]\) 表示考虑前 \(i\) 位，各个容斥统计子问题带上对应系数后的答案之和，它向后的转移很简单，容斥系数乘上不合法位置填法的系数。
从一般的动态规划思路也可联想到这种方案，其实末尾数字是一个多余的信息，可以不用记录，用容斥的思想即可正确转移，直接设 \(dp[i]\) 表示考虑前 \(i\) 位的答案。
\(dp[i]->dp[i+1]\)，可以任意填，有算重。
考虑钦定 \(dp[i]->dp[i+1]\) 这里不合法，那么减去 \(dp[i-1]*(i\ 到\ i+1\ 不合法的方案数)\)。
发现减多了，因为 \(i-1\rightarrow i\) 时不合法的也被减掉了，但这一部分贡献根本在第一次就没加上。
继续推下去和容斥的思路也完全一样了。
容斥原理的统计过程，是可以用动态规划来完成的，注意转移时需要带上容斥的系数，相当于把不同的不合法条件数的统计过程压缩到了一次，带上容斥系数就是压缩信息的过程。
T2
T3
My Method
将差分数组的所有值视为一个集合。
它本质上需要计算第 \(k\) 大元素的期望。
很容易想到min-max
容斥，问题变成了计算一个差分数组集合子集最小值的期望值，考虑怎么算一个子集最小值的期望值。
假设子集为 \(S\)，枚举最小值的取值 \(x\)，然后问题变成了有多少个长度为 \(n+1\) 的序列 \(a\)，满足 \(a_i\ge 1,\sum a_i=m+1,\forall p\in S, a_p\ge x\)，这是一个先把 \(S\) 中所有元素的限制变成 \(\ge 1\)，方法是把 \(\sum\) 变成 \(=m+1-size(S)\times(x-1)\)，剩下的是个插板法。
因此对于大小相同的子集这个值是一样的。
记 \(val_k\) 表示大小为 \(k\) 的子集，最小值的期望。
接下来可以直接套 min-max
容斥的公式，但是我背不住那个公式，于是考虑比较暴力的方式，考虑所有大小为
\(n-k+1\) 的子集的期望最小值的和。\(k\) 小值贡献了 \(1\) 次，\(k-1\) 小值贡献了 \(\binom{n-k+1}{n-k}\) 次，\(\cdots\)，边界是最小值，一路推上来就行。
复杂度 \(O(nm+n^2)\)
Talentkk's Method
Solution
min-max 容斥
T4
\[ (\dfrac{\alpha v}{\beta v})_T=T(\frac{\alpha p}{2 T})_v - P \]