欢迎来看 “片” （的简介）

由于-\(看片\)-生涯转瞬即逝，于是我选择对“\(片\)”进行一定的总结：

相信你一定看懂了

由于开始的时间有一点晚，就姑且认为我以后会慢慢补充吧......

\(CF1789F\) \(Serval\) \(and\) \(Brain\) \(Power\)

解：DP
见过狗的，没见过这么狗的：
分 \(3\) 类讨论：
首先对于偶数的，我们显然可以直接枚举两串的长度，
其次，对于 \(3\) 的，可以进行上述相同的操作，只不过是区间分为3段
最后，对于\(\geq\) \(5\) 的奇数，进行“二进制拆分”即可

\(CF1781F\) \(Bracket\) \(Insertion\)

解：DP
考虑转移这个恶心的东西，首先吧 “\((\)” 和 “\()\)” 变成 \(1\) 和 \(-1\)
这个时候，我们可以发现个合法的序列要满足任意部位
大于等于前缀和 \(0\)，结尾前缀和为 \(0\)（这个不用管），
然后有一种想法，我们考虑一个数往后它的贡献，
这个时候，当前的 \(f\) 由后面的操作而来，这个时候，
设当前这一位的前缀和为 \(x\)，有 \(1\):
不妨吧每一次操作拆开，那么 \(1\) 行为就是把当前以为改为 \(x\) , 后两位为 \(x+1\), \(x\)
反之，对于 \(2\) 行为，就有 \(x\), \(x-1\), \(x\)
就可以放心操作不用管，此时，有方程，当前：

$f_{n,k}=\displaystyle\sum_{i=0}^{n-1} \displaystyle\sum_{j=0}^{n-i-1} C_{n-1}^i C_{n-i-1}^j \times p \times f_{i,k} \times f_{j,k+1} \times f_{n-1-i-j,k} + $

\(\displaystyle\sum_{i=0}^{n-1} \displaystyle\sum_{j=0}^{n-i-1} C_{n-1}^i C_{n-i-1}^j \times p \times f_{i,k} \times f_{j,k-1} \times f_{n-1-i-j,k}\)

意为：
往后 你 \(n-1\) 次选择，选i种第一种情况，\(j\) 种第二种情况，\(n-i-j-1\) 种第三种情况递推出当前情况

这是 \(n^4\) 的做法，然而，两个 \(\sum\) 可以化简

令 \(g_{n,k}=\displaystyle\sum_{i=0}^{n-1} C_n^k \times f_{i,n} \times f_{j-i,n}\)

放入原方程就有:
实际上，跟斜率优化一样，上面那个只是把 \(j\) 提了出来

\(f_{n,k}= \displaystyle\sum_{j=0}^{n-1} C_{n-1}^j \times g_{{n-1-j},k}\times（p \times f_{j,k+1} + (1-p) \times f_{j,k-1}\)