看题解系列

首先是异或差分（其实我也不知道叫什么）
定义f 为异或数组

$$f\left [ i \right ]=w\left [ i \right ]\ xor \ w\left [ i+1 \right ]$$

表示$w\left [ i \right ]\$ 与$\ w\left [ i+1 \right ]$ 是否相同
f 数组中至多有 $2k$ 个 1 ，且肯定是偶数个
当f 数组全部为0 时，灯全部点亮
对于一段连续序列进行翻转，显然只需要修改$f\left [ l-1 \right ]$，$f\left [ r \right ]$
这个操作等价于对某个元素进行移动
当两个1 相遇时会消除
于是问题等价于求所有1 消除的代价
对于任意两个1 消除的代价，可用完全背包求
将长度为len 的操作看成len 和-len 两种
最后状压所有1

$$dp\left [ s' \right ]=min\left \{ dp\left [ s \right ] +cost\left [ i,j \right ]\right \}\left ( i\notin s,j\notin s \right )$$

乍一看枚举i ，j 复杂度$O\left ( 2^{N}N^{2} \right )$
但实际上其中一个并不用枚举，确定任意一个i 之后枚举j 即可
因此复杂度$O\left ( 2^{N}N \right )$

证明省略

$$Lucas\left ( m,n,p \right )=C\left ( m\%p,n\%p \right )*Lucas\left ( \left \lfloor \frac{m}{p}\right \rfloor ,\left \lfloor \frac{n}{p} \right \rfloor ,p \right )$$ $$Lucas\left ( m,0,p \right )=1$$

$n+1$个点可以唯一确定一个$n$次的多项式
当然可以用高斯消元解，但复杂度是$O\left ( n^{3} \right )$的
这里引入拉格朗日插值法

拉格朗日插值法

对于$x_{i}$，假设有多项式$\ell_{i}$

$$\ell_{i}\left ( x \right )=\left\{\begin{matrix} 1 \ \left ( x=x_{i} \right ) \\ 0 \ \left ( x\neq x_{i} \right ) \end{matrix}\right.$$

则

$$y_{i}\ell_{i}\left ( x \right )=\left\{\begin{matrix} y_{i} \ \left ( x=x_{i} \right ) \\ 0 \ \left ( x\neq x_{i} \right ) \end{matrix}\right.$$

不难得出

$$\forall k\leq n+1 ,\sum_{i=1}^{n+1} y_{i}\ell_{i}\left ( x_{k} \right )=y_{k}$$

即该多项式经过所有$n+1$个点

考虑如何构造$\ell_{i}\left ( x \right )$
显然如下构造可行

$$\ell_{i}\left ( x \right )=\prod _{i\neq j}\frac{\left ( x-x_{j} \right )}{\left ( x_{i}-x_{j} \right )}$$

对于每个$x_{j}\left ( i\neq j \right )$，分子中都会出现$0$
而将$x_{i}$带入时，分子分母完全相同

化简可得

$$f\left (x \right )=\sum_{i=1}^{n+1}y_i\prod_{j\neq i}\frac{\left ( x-x_{j} \right )}{\left (x_{i}-x_{j} \right )}$$

单次求值复杂度$O\left ( n^{2} \right )$

重心拉格朗日插值法

不难发现$\ell_{i}\left ( x \right )$有重复计算部分
设

$$\ell\left ( x \right )=\prod_{i=1}^{n+1} \left ( x-x_{i} \right )$$ $$w_{i}=\frac{1}{\prod _{i\neq j}\left ( x_{i}-x_{j} \right )}$$

不难得到

$$\ell_{i}\left ( x \right )=\ell\left ( x \right )\frac{w_{i}}{x-x_{i}}$$

化简可得

$$f\left (x \right )=\ell\left ( x \right )\sum _{i=1}^{n+1}y_{i}\frac{w_{i}}{x-x_{i}}$$

单次求值复杂度还是$O\left ( n^{2} \right )$
当动态加入点时，一般拉格朗日插值法需要$O\left ( n^{2} \right )$重新计算，而重心拉格朗日插值法只需$O\left ( n \right )$计算一遍$w_{i}$

对于一个$\left ( L,R \right )$的区间
若其中最大值位置为k
所有可行解可以分为三类

• i，j 在k 的两边
• i，k 或者k，j
• $\left ( L,k-1 \right ),\left ( k+1,R \right )$区间内

对于最后一种递归计算即可

对于第二种只需统计1 的个数

对于第一种
若$\left ( L,k-1 \right ),\left ( k+1,R \right )$均已升序排序
枚举其中一个区间
则另一个区间中可以匹配的元素单调递减
因此可以在线性时间内完成统计
至于怎么对$\left ( L,k-1 \right ),\left ( k+1,R \right )$进行排序，归并即可

最优复杂度$O\left ( NlogN \right )$
然而只要一组升序的数据就能卡成$O\left ( N^{2}\right)$

很巧妙的一道题

设$f\left [ i \right ]\left [ u \right ]\left [ v \right ]$为u 到v 之间是否存在长度为$2^{i}$的路

$$f\left [ i \right ]\left [ u \right ]\left [ v \right ]=f\left [ i -1\right ]\left [ u \right ]\left [ k \right ]\ and \ f\left [ i -1\right ]\left [ k \right ]\left [ v \right ]$$

设$d\left [ u\right ]\left [v \right ]$为u 到v 需要的时间

$$\exists f\left [ i \right ]\left [ u \right ]\left [ v \right ]=1,d\left [ u\right ]\left [v \right ]=1$$

最后跑一遍Floyd 即可

考虑第i 个和第i+1 个位置

$$max\left \{ \frac{pre}{R_{i}} \frac{pre*L_{i}}{R_{i+1}} \right \}$$

交换之后则为

$$max\left \{ \frac{pre}{R_{i+1}} , \frac{pre*L_{i+1}}{R_{i}} \right \}$$

其他人的并没有改变
提取pre

$$max\left \{ \frac{1}{R_{i}} , \frac{L_{i}}{R_{i+1}} \right \}\quad \quad \quad max\left \{ \frac{1}{R_{i+1}},\frac{L_{i+1}}{R_{i}} \right \}$$

同乘$R_{i}*R_{i+1}$

$$max\left \{ R_{i+1} , L_{i}R_{i} \right \}\quad \quad \quad max\left \{ R_{i}, L_{i+1}R_{i+1} \right \}$$

L,R 均为正整数

$$R_{i}< L_{i}R_{i} \quad \quad \quad R_{i+1}< L_{i+1}R_{i+1}$$ $$L_{i}R_{i} \quad \quad \quad L_{i+1}R_{i+1}$$

因此将$L*R$较小的放在前面更优

人生苦短，我用Python

经典的状压DP题，解法很多
这里讲下状压轮廓线的做法

s 从大到小保存
若$s_{5}=0$，必须要竖放一个
否则可以横放也可以不放

支配树的证明我意会了一下，并不会证
这里稍微理一下DAG中支配树的构造

• 拓扑排序
• 对于每个点，求其所有入边的LCA，将其作为LCA的儿子

首先预处理出可可在点s ，聪聪在点i 时，聪聪的下一步
对每个s 做一遍单源最短路，枚举所有点i 的出边，选择其中距离较短且序号较小的点作为下一步
设$p\left[u\right]\left[v\right]$为聪聪在点u 可可在点v 的期望步数

• u=v ，$p\left[u\right]\left[v\right]=0$
• 当前回合能抓到，$p\left[u\right]\left[v\right]=1$
• 其他情况
  设x 为聪聪下一步 $$p\left[u\right]\left[v\right]=\sum\frac{p\left[x\right]\left[to\right]}{k+1}+\frac{p\left[x\right]\left[v\right]}{k+1}+1$$

记忆优化搜索即可

观察到m 比较小
考虑记录每行所有状态

• m=1
  dp 数组记录第i 行，放了j 个，当前行放1 不放0

  $$dp\left[i\right]\left[j\right]\left[0\right]=max\left( dp\left[i-1\right]\left[j\right]\left[0\right] ,dp\left[i-1\right]\left[j\right]\left[1\right]\right)$$ $$dp\left[i\right]\left[j\right]\left[1\right]=max\left( dp\left[i-1\right]\left[j\right]\left[1\right] ,dp\left[i-1\right]\left[j-1\right]\left[0\right] ,dp\left[i-1\right]\left[j-1\right]\left[1\right] \right)+w\left[i\right]\left[1\right]$$

• m=2
  0 表示两格均不放
  1 表示放左边
  2 表示放右边
  3 表示两格均有，且为两格个矩形
  4 表示两格均有，且为一个矩形
  转移方程因为空间问题（懒），请看代码