牛客练习赛27-F
题意：见上。
$m$小考虑状压，$n$大考虑矩阵优化
$dp(i,j)$为合法$i$转移到合法$j$状态的方案数，其中状态是当前位置为$i$, 区间$[i-m+1,i]$填$3, 7$情况，判断一下就可以构造转移矩阵，然后发现转移可以看做Floyd的联通矩阵，题面就要求某个点开始的环的个数。
那么矩阵快速幂一下，再加上对角线的值即可(加上每个点出发环的个数)

另外可以用常规DP方法做，快速幂次数就进行$n-m$次，之后将末尾和前面check一下即可

牛客国庆集训派对Day2 E数据排序
题意：见上。

这种题一般都是按从小到大赋值$c$。我们可以设$dp(S)$为前面已经赋值的最小值。

然后我们就可以枚举剩下元素的子集来加入，这个子集所有元素都是一个值，且大于之前所有的值。

那么我们可以预处理出来前面一个求和，后面的求和也可以预处理。

前面的求和先预处理出一个点对一个集合的，再在DP过程中从小到大去转移集合对集合的。用最高位转移。这样可以免去枚举一个$n$，具体可以看代码中的$p$

知识点：
1、状态设计方法
2、lowbit/最高位转移

牛客Wannafly挑战赛19 C多彩的树
题意：有一棵树包含 $N$ 个节点。节点总共有 $K$ 种颜色。第 $i$ 个节点的颜色为 $A_i$。
求恰好包含 $i$ 种颜色的路径数量 $F_i$。

这个恰好我们可以用容斥来做。
考虑一条条路径不方便处理，我们考虑路径就是两个块之间的任意连线。
那么我们发现颜色数小，可以状压，我们每次枚举一个集合表示当前许可进入的颜色，然后在树中DFS，DFS到的一个块里面的路径都是符合当前许可进入的颜色的，然后我们只需要进行容斥就可以计算出在某个连通块中出现恰好包含 $i$ 种颜色的路径数量。

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$一开始是$∅$, 现在支持插入一个数/删除一个点，并且这个点一定只会插入一次删除一次，求每次操作完后集合$\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)$
3、类斐波那契数列 $h(n)=a \times f(n-2) + b \times f(n-1)，a=h(1), b=h(2)$

例题

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、构造一个数列，可以构造他的前缀和 (升次)