前言

质量还可以

D.容斥(二项式反演)

题目大意:

给你$n$个小球，每个小球有一个颜色$a_i$.保证一种颜色最多出现两次。问你多少种排列方式使得相邻两项之间颜色不同.
$n\le 1e5$

题目思路:

发现颜色最多出现两次.我们可以容斥。将恰好转至少.

令$f(i)$为恰好有$i$项相邻的排列,$g(i)$为至少有$i$项相邻的排列.$cnt$为有两个的颜色个数.

$f(0)={\sum }_{i=0}^{cnt}(?1{)}^i?g(i)$.

$g(i)$就比较好求了:$g(i)={(}_i^{cnt})?(n?i)!?\frac{1}{2^{cnt?i}}$

解释:
1.至少$i$个相邻,那么就得先确定哪$i$个颜色相邻.所以${(}_i^{cnt})$.
2.然后问题转化为:总共$n$个小球。有$i$对个颜色不同的物品两两捆绑在一起，其他位置都是不同颜色的物品，求他们的全排列.根据一一映射的原理,方案数为$(n?i)!$.
3.但是剩下的这$n?i$个物品中实际上还是有$cnt?i$对小球是颜色相同的，根据可重复排列的原理，我们还需要把重复的部分除掉。即$\frac{1}{2^{cnt?i}}$.

最后，这题还卡常。我们需要对阶乘$O(n)$的求解逆元.

E.思维+sosdp

题目大意:

给你只含$2^x$的序列.你可以反转任意子区间。问你最大子段和，使得里面没有重复的数,

题目思路:

重点:将任意一个子区间反转意味着能够将两个子区间拼在一起

2.由于要求了一个区间不能有重复的数，那么合法的区间数不超过$nlogn$.直接预处理出来。

那么接下来，我们就是枚举每一个区间，每个区间可以被表示成一个二进制数,

那么将每一个合法区间写下来生成一个新的序列$b_i$.问题转化为:

枚举$b_i$,快速找$b_j$满足$b_i\&b_j=0$，并且$b_i$