BZOJ 3294
题意：在一个$n$行$m$列的棋盘里放$c$种不同色的棋子（每种有$c_i$个），使得每个格子最多放一个棋子，且不同颜色的棋子不能在同一行或者同一列。有多少种方法？

本题发现其实列或者行交换不影响答案，那么我们可以设个$dp(i,j,k)$为前$k$个颜色占据了$i$行$j$列的方案。
那么可以转移
$$
dp(i,j,k)=\sum_{x=1}^i \sum_{y=1}^j dp(x,y,k-1) \times C^{i-x}_{n-x} \times C^{j-y}_{m-y} \times g(i-x,j-y,a_k)
$$
其中$a_k$为第$k$种颜色有几个棋子，$g(i,j,k)$为$k$个相同棋子占据了$i$行$j$列的方案。
考虑如何计算$g$，我们只用将不符合条件(即不占据$i$行$j$列时已经用完棋子)的情况减去即可，容易得总情况数目为$C_{ij}^n$
那么转移
$$
g(i,j,k)=C^{k}_{ij} - \sum_{x=1}^i \sum_{y=1}^j g(x,y,k) \times C^x_i \times C^y_j
$$
那么就可以递推求解了。

知识点：
1、容斥
2、dp的辅助dp数组

BZOJ 5314
题意：见上。

设$dp(u,j,0/1,0/1)$为$u$子树放了$j$个，$u$放不放，$u$有没有信号的方案。

然后按照树形背包DP的方法转移即可，注意要用$dp[u][i+j][][] \Leftarrow dp[u][i][][], dp[v][j][][]$来保证复杂度。

这种树形背包dp就是形如$dp[x][j+k]=\sum dp[x][j] \times dp[y][k]$的

这里有对这样的树形背包dp复杂度为$O(nk)$的证明。证明用了一个基本性质即在$\text{LCA}$上算贡献，可以将复杂度$O(n^3)$分析到$O(n^2)$

Codeforces 1140F
题意：$S$一开始是$\empty$, 现在支持插入一个数/删除一个点，并且这个点一定只会插入一次删除一次，求每次操作完后集合$\text{E}(S)$的大小。$\text{E}(S)$集合一开始是当前的$S$, 如果$(x_1,y_1) \in \text{E}(S), (x_1,y_2) \in \text{E}(S), (x_2,y_1) \in \text{E}(S), (x_2,y_2) \notin \text{E}(S)$，那么$(x_2,y_2)$被加入到$\text{E}(S)$中，一直操作直到没有为止。

这题类似 CF 某场 EJOI 的题，我们发现将$(x,y)$看做连边，则答案就是一个联通块的$x,y$值域之积。

然后我们就可以维护并查集，但是这里有删除，我们联想到可撤销并查集

但是并不好用，因为一个数对有效范围是一个区间。

所以我们想到用线段树来优化($\log$级优化)，类比于线段树优化连边

即我们开一棵线段树，把每个数对有效区间在线段树上打好标记，然后我们可以按$\text{dfs}$序来遍历线段树，每次遍历到线段树的一个区间，暴力插入当前区间上所有有标记的数对，然后之后退出这个点再暴力删掉。由于线段树上一个大区间会被分成$\log$级别的小区间，然后每个修改最多操作$\log n$次，那么就符合时间复杂度了。

这种线段树优化的方法很好，以后一些整区间的优化可以联想到线段树划分区间来优化，其实和线段树优化连边思路有相似点，都是利用线段树上一个大区间会被分成$\log$级别的小区间来优化复杂度。

模板及讲解

通项公式

$$
F(n)=\frac{1}{\sqrt 5}\left[\left(\frac{1+\sqrt 5}{2}\right)^n - \left(\frac{1-\sqrt 5}{2}\right)^n\right]
$$

技巧

1、斐波那契数列增长快
2、与斐波那契数列相关的大数据递推，可以用矩阵优化

恒等式

1、$f(1)+f(2)+f(3)+ \dots +f(n)=f(n+2)-1$
2、$f(1)^2+f(2)^2+f(3)^2+ \dots +f(n)^2=f(n)f(n+1)$
3、$f(1)+f(3)+f(5)+ \dots +f(2n-1)=f(2n)$
4、$f(2)+f(4)+f(6)+ \dots +f(2n)=f(2n+1)-1$
5、$f(m)f(n-m+1)+f(m-1)f(n-m)=f(n), n \leq m$
6、$f(n-1)f(n+1)=f(n)^2+(-1)^n$

性质

1、$\gcd(f(n), f(m))=f(\gcd(n, m))$
2、$n | m \Leftrightarrow f(n) | f(m)$

例题

P1306 斐波那契公约数

运用$\gcd(f(n), f(m))=f(\gcd(n, m))$缩小范围再矩阵快速幂优化。

Codeforces 1167E
题意：给定一个序列$a_i$，求有多少种在$a$中取$a_i \in (-∞, l] \cup [r, +∞)$的方案使得取出来的数是增序排序的。

我们考虑分开两边处理，发现左边如果使$l$单调递增，那么右边的$r$也是单调递增的。

所以我们可以考虑双指针来做。

$l$增加的过程中，不能存在$a_i \in (-∞, l]$不有序的情况。$r$即为满足$a_i \in (-∞, l] \cup [r, +∞)$的最小$r$

那么我们这样就可以算方案了。

判断加进来的数能不能有序，就每个数记录一个最大出现位置和最小出现位置，判断一下大小关系即可。

知识点
程序出错的原因
1、大思路就出错了 —— 重构
2、程序上有bug —— 检查程序
3、思维上有bug —— 出数据，想特殊情况
一般情况下，错误先看程序上是否写错，然后再看思维上是否有漏洞，否则就考虑一下是否大思路是有误

BZOJ 3622
题意：给出 $n$ 个数 $a_i$，以及 $n$ 个数 $b_i$，要求两两配对使得 a > b 的对数减去 a < b 的对数等于 $k$ 。保证 $a,b$ 无相同元素。

我们可以计算出a > b的对数，我们可以算出他是$\frac{k+n}{2}$，方便起见我们让$k=\frac{k+n}{2}$

如果前面的式子不能整除则无解

然后我们考虑容斥，将$a,b$从小到大排序，我们可以设$f(i,j)$为前$i$个位置有$j$对a > b，其他的没有考虑的方案数。

注意这里$f(n,k)$不是答案，因为没有考虑其他的位置

设$l_i$ 为$a_i \geq b_j$的最大$j$，则有转移方程
$$
f(i,j)=f(i-1,j)+f(i-1,j-1)\times (l_i-j+1)
$$
$l_i$相当于当前$i$的所有决策点，这些点一定包括之前的$i$的所有决策点，所以减去$j-1$就可以保证不重复。

然后我们将其他位置安排下来，设$F(i)=f(n, i) \times (n-i)!$

设最后的答案为$g(i)$，则$g(i)$对每个小于$i$的$F$有贡献。

则
$$
F(i)= \sum \limits_{j=i}^{n} C^{i}_{j} \times g(j)
$$

根据二项式反演，则有
$$
g(i)= \sum \limits_{j=i}^{n} (-1)^{j-i} \times C^{i}_{j} \times F(j)
$$

Codeforces 1174D
题意：给两个数$n$和$x$，构造一个满足以下条件的序列：
对任何$a_i, 1 \leq a_i \leq 2^n-1$, 序列中没有非空连续子序列异或和为$0$或$x$序列长度$l$应该最大

其实发现对于子序列来说这题会很好做

然而我们可以构造这题的前缀和，然后就转化成子序列问题

然后依次填即可。

知识点：
1、构造一个数列，可以构造他的前缀和 (升次)

Codeforces 1181D
题意：

考虑将每个国家的举行次数排序，然后按顺序离线去做即可，可以看代码注释方法。
注意要求$k$大，可以Splay，但是可以更方便的用树状数组来求

知识点：
1、思维要清晰

Codeforces 1163E
题意：给定$n$个区间$[l_i, r_i]$，$m$次询问用最小的区间覆盖$[x,y]$

发现对于一个点，所有包含他的区间只有$r$最远区间的有用，因为直接选这个区间一定最优
所以我们可以用并查集或者线段树预处理每个点所有包含他的区间最远的$r$，然后我们就可以一步步的跳然后找到答案。
这里一步步跳，我们联想到倍增优化，那么预处理一下倍增即可。
但是这里还要考虑一下不存在方案的情况。
那么对区间在轴上区间增加，如果一个地方的值等于0说明这中间断开了，处理一下即可。
更好的实现我们考虑一个区间，所有和他相交区间只有$r$最远区间的有用，按照上面的方法处理一下即可。

知识点：
1、需要跳的题面可以考虑倍增优化

BZOJ 4665
题意：求有重复元素排列的错排。

考虑将所有元素都看成不同的(重复元素也看做)，然后最后再除以各自的个数消序即可。

然后我们考虑设$F(i)$为至少有$i$个位置上是原来的数，那么我们可以利用这个来容斥，即
$$
\text{ans}=\sum_{i=0}^n F(i) \cdot (-1)^i
$$

我们考虑怎么求这个$F(i)$，设$dp(i,j)$为前$i$个值全部考虑完，至少有$j$个位置上是原来的数的方案，那么

$$
dp(i,j)=\sum_{k=0}^{min(j,cnt[i])}dp(i-1,j-k) \cdot C_{cnt[i]}^{k} \cdot \prod_{p=cnt[i]-k+1}^{cnt[i]}p
$$

其中$cnt[i]$为值$i$的元素个数。
那么我们可以得到
$$
F(i)=dp(n,i)\cdot (n-i)!
$$
那么就能容斥了。