<span>杂题</span>

1.容易发现题意中的子序列没啥用，其实要求的是集合个数。

然后考虑并不是所有的点对都是需要关注的，处理的方法是把所有的数按照大小排序。

其实按照大小排序就是 $0/1 tire$ 树的样子，所以这样做的话，

一个集合中的两两最小异或值实际上就是按照顺序的两两异或值的最小值。

然后只要考虑每个数能通过哪些数转移就行了，可以写一个 $0/1 tire$ 树来解决。 

2.容易发现取模的式子可以换成减法，于是发现 $\frac{n}{i}$ 这个玩意可以整除分块。

写出来式子，发现就是约数和函数，那直接搞就完了。

3.这类平方串问题的一个套路似乎就是枚举平方串长度为 $2*len$。

然后每 $len$ 长度设一个关键点，每个平方串肯定是跨过恰好两个关键点。

所以枚举相邻的关键点，求出 $lcp,lcs$ 直接计算合法的平方串。然后根据调和级数可以证明复杂度。

问题是咋搞那个权值，如果不考虑那个前导 $0$，肯定算个前缀和然后直接区间查询就完事了。

然后对于前导 $0$，思路是将平方串的权值拆成 $w+w*10^{len}$，然后考虑计算平方串的前一部分的权值 $w$。

方法是这样的，如果 $string_{i+1}=0$，就强行让 $sum_i$ 取值为 $0$。

这样因为平方串中的前导 $0$ 出现了 $2$ 次，所以算得的恰好是 $0-0$。

4.求满足不下降的n个的变量，但是最后一项确定的序列方案数。

对原序列进行差分操作，于是问题转化为求和为确定值，每一项的值为非负数。

这个直接用插板法组合数计算。

5.将 $n$ 个元素分成 $m$ 组，求 $\sum \prod \limits_{i=1}^m \binom{x_i}{k_i}$。

首先组合数可以通过实际含义转化为取互不相同的关键点。

然后似乎并不是很好搞，考虑把关键点也转化成分组的形式，实际上就是每个关键点对应新的一组。

然后问题就又是分组，还是用组合数就行了。

6.把期望的次数摊到其他组先被丢掉的概率上，然后就是一个简单的分数。

把总次数摊到每个数被选择的概率上，这个概率就是没有任何一个因子被选中的概率，也是一个简单的分数。

7.将期望经过的次数转化为分别考虑三种球。

其中蓝球给定了，绿球因为与蓝球的相对概率始终不变，直接乘上一个系数即可。

对于红球，可以分别考虑每一个，然后每一个与选择蓝球的相对概率是不变的。

所以这个红球每次不被选择的概率就是 $\frac{B}{B+1}$，对这个做 $k$ 次方就是最后也没被选中的概率。

8.首先可以转化为每个未被确定的游戏获胜的概率。

然后这个东西只和左右第一个被确定的结果有关。

对于确定了左边的 $A$ ，右边的 $B$ ，中间有一个事件 $X$。

要计算的是 $P(X|(A \ and \ B))$。

有 $P(X|(A \ and \ B))=\frac{P(X \ and A \ and \ B)}{P(A \ and \ B)}=\frac{P((X \ and \ B)|A)P(A)}{P(B|A)P(A)}=\frac{P((X \ and \ B)|A)}{P(B|A)}$。

化到这个式子，问题已经是只有左侧对右侧产生贡献。

写一个简单的 dp，然后用线段树维护转移矩阵优化一下就行了。

9.AGC035D

考虑把问题逆向考虑，然后把不断更新数组转化为每个原数组乘系数的形式。

首先 $1,n$ 的系数肯定为 $1$。

然后考虑取得一个 $mid$，此时 $mid$ 的系数一定为 $2$。

更加一般的，对于 $l,r$ ，$coef_{mid}=coef_l+coef_{r}$。

然后取得 $mid$ 之后，问题转化为子问题，可以递归求解。

所以记录四个信息，分别是左右端点，左右端点的系数即可。

因为对于左右端点的系数的状态，一个状态只能更新到至多两个状态，并且深度不超过 $n$，所以状态数并不多。

10.CF756F

考虑一个右端点 $r$ ，能产生贡献的满足 $a_l \leq a_r$ 的左端点 $l$。

然后取出所有位置、权值分别单调的 $l$。

对于相邻的两个左端点 $p<q$，如果 $a_r-a_p>a_p-a_q$ ，那么 $p$ 是无用的，因为在 $p,q$ 处已经有了更优的决策。

所以每次权值都能减半，这样可以处理出 $nlog$ 个点对，扫描线一下就结束了。

11.考虑 $l=0$，并且 $n$ 并不大的情况。

每次只要考虑是否所有位都卡住了上限，如果是就递归下一位。

否则存在一个数没卡住上限，那么只要这一位合法。

除了第一个没卡住上限的数，其他数可以随便选择，最后只要那个没卡住上限的位来强行补成 $k$ 就好了。

因为每个数的 $l,r$ 都是相同的，所以可以矩阵优化。

对于 $l \neq 0$，其实容斥来搞一下即可。

主要的思想是只要关注钦定的集合的大小的奇偶性，然后仍然分卡满和存在一个没卡住上限的位两种情况用矩阵转移即可。

12.Short LIS

对于一种特殊的排列，几种等价的描述是：

最长下降子序列不超过 2.

冒泡排序次数达到下界。

可以划分为不超过 2 个子序列，满足单调上升。

对于每个元素满足：要么前面的数都比他小，要么比他小的数都在他前面。

与一种前缀 $\max$ 序列一一对应。

这道题只要计数最后一种情况。

考虑现在令 $a_x=y$。

如果说 $y \geq x$，那么分析可知 $a_x$ 一定在前缀 $\max$ 上，否则也可分析知 $a_x$ 一定不在。

对于不在的情况，对原排列进行一些操作可以转化为前者。

然后原问题转化为前缀 $\max$ 序列的计数，写一下要满足的条件，弄一个类似卡特兰数的翻转就解决了。

13.多次翻折法

与卡特兰数类似，但是给定两条直线，分别表示上界和下界。

首先容易计算总方案，然后问题还是如何把方案数凑出使得不合法的方案贡献恰好为 $1$。

这里的方法是枚举两种情况：第一次从上边界出界、第一次从下边界出界。

然后每次都强制计算从与上次不同的边界出界，并使系数不断从 $1,-1$ 之间变换，方案数就是不断把最终给定节点按照非法直线翻转。

这样对于一个非法的方案，在一种中系数贡献为 $1$，另一种中为 $0$，二者相加就达到了要求。

14.Jiry Matchings

首先考虑如果问题是链上求所有方案的和。

做法是一个分治，就是令 $A_{l,r,0/1,0/1}$ 表示考虑了区间 $[l,r]$，分别记录左右端点状态的多项式。

每次的操作就是分治左右，然后把多项式合并。

如果形态是树，做法是这样的。

考虑首先重链剖分，然后对于一条重链上的所有点，首先通过分治处理轻边贡献。

然后再进行像链上一样的分治过程把重链信息合并起来。

对于取最大值，其实可以发现这样一个事情，通过费用流的做法可以证明，函数是凸的。

然后每次的操作其实就是 $\max\  add$ 卷积，在这种操作下，凸函数的卷积仍然是凸函数。

考虑给参与卷积的两个函数差分一下，然后直接归并得到的就是结果。

15.小星星

子集反演一下就是只需要保证每个点的标号都是集合内的数，这个东西简单 dp 就可以实现。

所以枚举子集然后乘上容斥系数就好了。

16.Ribbons on Tree

每条边都覆盖即恰好没覆盖 $0$ 条边，可以用枚举子集钦定 $i$ 条边没覆盖容斥得到。

然后就划分得了若干个连通块，每个连通块是独立的，所以可以 dp。

然后对于每个连通块，权值就是依次选择匹配位置，实际上就是一个简单的双阶乘。

17.青春猪头少年不会梦到兔女郎学姐

首先考虑序列上的做法，大概的思想还是对于每种颜色钦定形成了若干个连通块然后容斥。

但是比较难搞的一点是，这里容斥的不是方案数而是权值，所以直接针对方案数的那种简单容斥方法不奏效了。

然后正解的做法是，将容斥系数直接拆分到每个颜色里面，推一推式子可以发现这样用原来的做法也能做。

然后下一个问题是怎么处理环上的贡献，这个的做法也很巧妙。

考虑首先计算第一个位置颜色为 $1$，并且最后一个位置颜色不为 $1$ 的权值总和。

进行容斥，用第一个位置出现颜色为 $1$ 的权值总和 减去 第一个位置和最后一个位置出现颜色均为 $1$ 的权值总和。

当时颓题解的时候这个地方一直没想明白，因为这里权值并没有考虑环上首尾相接的贡献。

其实这并不重要，因为最终要求得的答案中是不存在首位相接的贡献的，所以减数和被减数都无视掉这种情况，得到的自然是对的。

根据题意可知，要求每个环的计数次数为这个环的循环节长度。

然后考虑一个环方案的权值已经被计数了  颜色为 $1$ 的连通块个数 / 循环节个数  次。

所以只要修改一下颜色 $1$ 的 $EGF$，把颜色为 $1$ 的连通块个数除掉，再乘上一个总长度即可恰好计数循环节长度次。