lg P5598 混乱度
考虑用卢卡斯定理展开成\(k\)进制来做
对于每一个位置网后枚举维护和计算后缀答案，如果某一位发生了进位显然答案就会变成\(0\)
于是分成若干段做即可，将所有\(0\)的位置压缩并且每个数只枚举\(p\)进制有值的位置，这样复杂度就是\(O(nplog)\)的了
显然只有二叉树才合法
考虑\(f[u]\)表示\(u\)的子树，只填在\(u\)所填这一列即之后的方案数
如果两个儿子，枚举哪个向下一步
加上较长的那一个和较短的挨着走后的下个的答案即可
对于一个儿子\(v\)
要么接到下面，要么右边加上\(f[v]\)后需要考虑的就是某一条链拼回\(u\)下面的情况
大力分类讨论以及判不合法的即可
显然是下凸的，二分后贪心即可
比较蠢写的两个\(log\)
考虑用斐波那契数系表示
记所有为\(1\)的位置为\(b\)
考虑\(dp,f[i]\)表示前\(i\)个当前这个不下放\(b_{i-1},b_{i-2}\)的方案
\(g[i]\)表示要下放的
那么\(f_i=f_{i-1}+g_{i-1},g_{i}=\frac{b_i-b_{i-1}-1}{2}f_{i-1}+\frac{b_i-b_{i-1}}{2}g_{i-1}\)
发现\(b\)差分后可以写成矩乘形式
有插入用平衡树维护
另外再用\(set\)之类的维护连续\(01\)交替段
对插入\(ps\)分四类讨论：
1.\(a_{ps-1},a_{ps},a_{ps+1}=0\)直接插入
2.\(ps-1\)接着一个连续段
3.在一个连续段内\(0\)位置
4.在一个连续段\(1\)位置
然后维护\(del_b\)即可，讨论挺恶心的
维护一下前缀和之类的东西再差分一贡献即可
原文：https://www.cnblogs.com/KamiyamaShiki/p/12790573.html