做题汇总 - 洛谷保存站

$${\large \color{Red}重要的不是你做了多少题，而是你放了多少心思进去。}$$

目前整理：3.3至7.31，[链接](https://www.luogu.me/article/vu3wcowr)
# 搜索
## 深度优先搜索
### [P1731](https://www.luogu.com.cn/problem/P1731)
题意：构造一个蛋糕，每一层都比上一层薄且小，给定总体积与层数，求最小表面积\
思路：爆搜+剪枝，枚举半径与高，同时记录上一次选的数和后面的层最小表面积与体积
### [P1763](https://www.luogu.com.cn/problem/solution/P1763)
题意：构造若干个形如 $\frac{1}{x}$ 的分数，使和为 $\frac{a}{b}$，并且个数最少，个数相同情况下最小得分数越大越好\
思路：
- 下界：$\frac 1 i \leq \frac a b \iff i\geq \frac b a$
- 上界：因为$\frac 1 i$ 后面得数都比它小所以 $\frac {Cnt-l+1} i \geq \frac a b\iff\frac {(Cnt-l+1)b} a \geq i$

优化：
$$\frac 1 x+\frac 1 y=\frac a b\\$$
$$\Rightarrow \frac{x+y}{xy}=\frac a b\\$$
$$\Rightarrow \frac {x+y}{xy}=\frac {ka} {kb} (k\in \Z)\\$$
$$\Rightarrow \left\{\begin{matrix} 
  x+y=ka \\  
  xy=kb 
\end{matrix}\right. 
$$
化简后有 $x^2-akx+bk=0$，这个方程有解情况为 $\Delta=a^2k^2-4bk\ge0$，则 $k\ge \left \lceil \frac{4b}{a^2} \right \rceil$，然后就能枚举 $k$ 使得 $\sqrt \Delta$ 为整数
### [CF208B](https://www.luogu.com.cn/problem/CF208B)
题意：初始 $n$ 张牌，当把两堆堆顶牌颜色或大小相等时，可以把两堆牌放在一起。现在每次只能把最后一堆放到倒数第二堆或倒数第四堆上，问最后能不能成为一堆\
思路：直接暴力搜索即可，记录当前有几堆与最后 $3$ 堆就行，即为 $(p,x,y,z)$，如果合并到倒数第二堆，那么从 $(p-1,p-3,x,z)$ 转移；如果合并到倒数第四堆，那么从 $(p-1,z,x,y)$ 转移。加一个记忆化，这样是 $n^4$ 的
## 广度优先搜索
### [P4667](https://www.luogu.com.cn/problem/P4667)
题意：给定一个电路图，一个格子的线是斜的\
思路：直接建图，如果是原来的线那么边权就是 $0$，否则就是 $1$。然后可以最短路或者双端队列搜索
### [P10481/P10482](https://www.luogu.com.cn/problem/P10482)
题意：填一个数字 $9*9$ 数独\
思路：将每个空格子按这个宫的数+这个行的数+这个列的数排序，从大到小一个一个填
### [P10485](https://www.luogu.com.cn/problem/P10485)
题意：一张图和一个 $1\times1\times2$ 的立方体，这个块可以立着或躺着。格子有坚固和不坚固和障碍物，不能立在不坚固的格子上，问最短走几步。\
思路：设定状态 $(x,y,p)$ 代表位置和状态（立着，横着躺，竖着躺）。预处理每个状态往四个方向移动后的状态，然后就能搜索了
# 贪心
## 构造
### [CF388B](https://www.luogu.com.cn/problem/CF388B)
题意：构造一个无向图，是的 $1$ 到 $2$ 恰好有 $k$ 条最短路\
思路：素质虫形每一节都多出来 $2$ 种走法，把 $k$ 二进制拆分，如果这一位为 $1$ 就把这一节连向 $2$，注意还要补几条边保证最短路长度相等即可
### [CF476D](https://www.luogu.com.cn/problem/CF476D)
题意：构造 $n$ 个四元组，每个四元组使用的数不重复，使得每组两两之间 $\gcd=k$，给出一个构造方法使得最大数最小\
思路：首先对于每一组相当于构造 $(ak,bk,ck,dk)$ 满足两两互质，考虑选什么，显然不能有两个偶数，只能选一个偶数，剩下选奇数，发现选相邻的 $3$ 个奇数 $\gcd=1$，所以可以选 $1,2,3,5$，下一次都 $+6$。最小值即为 $(6n-1)k$
### [CF488B](https://www.luogu.com.cn/problem/CF488B)
题意：给定 $n$ 个数，补成 $4$ 个数，使得 $\frac{a_2+a_3}2=\frac{a_1+a_2+a_3+a_4}4=a_4-a_1$，给出构造方案\
思路：化简后得 $a_1+a_4=a_2+a_3,5a_1+a_2+a_3=3a_4$。所以 $3a_1=a_4,a_2+a_3=4a_1$。分类讨论
- $n=0$，直接构造 $1,2,2,3$
- $n=1$，构造 $a_1,a_1,3a_1,3a_1$
- $n=2$
  - 若 $a_2 \le 3a_1$，构造 $a_1,a_2,4a_1-a_2,3a_1$
  - 否则无解
- $n=3$
  - 若 $a_3=3a_1$，构造 $a_1,a_2,4a_1-a_2,a_3$
  - 若 $a_3 \le 3a_1,a_2+a_3=4a_1$，构造 $a_1,a_3,a_3,4a_1$
  - 若 $a_1+a_2=\frac{4a_3}3$，构造 $\frac{a_3}4,a_1,a_2,a_3$
  - 否则无解
- $n=4$，直接判断
### [CF490D](https://www.luogu.com.cn/problem/CF490D)
题意：两个矩形，每次把一个矩形的一条边乘以 $\frac{2}3$ 或 $\frac{1}2$\
思路：先考虑 $3$ 再考虑 $2$，两个矩形哪个 $3$ 多就去掉哪个。最后考虑 $2$
### [CF534D](https://www.luogu.com.cn/problem/CF534D)
题意：给定一个序列 $a$，问能否重排后满足 $a_i=a_{i-1}+1-3k（k\ge 0）$\
思路：一直选 $k=0$，直到不行然后再减，重复即可
### [CF549D](https://www.luogu.com.cn/problem/CF549D)
题意：一个全 $0$ 矩阵 $a$，每次将一个包含 $(1,1)$ 的矩阵加上一个整数，求最少次数使得 $a$ 变成 $b$\
思路：从右下到左上看，这样就没有后效性。如果 $a_{i,j}\ne b_{i,j}$ 直接将 $(1,1)(i,j)$ 矩阵加上 $b_{i,j}-a_{i,j}$
### [CF550D](https://www.luogu.com.cn/problem/CF550D)
题意：构造一个图，每个点度数为 $k$，包含桥\
思路：把桥拆了之后就变成了两个有若干个度数为 $k$ 的点和 $1$ 个度数为 $k-1$ 的连通块。设大小为 $n$，如果 $k$ 为偶数，由于度数之和为 $n\times k-1$ 为奇数，而每个点贡献为偶数，所以不合法，所以 $k$ 是奇数，分成三个部分，一二各 $k-1$ 点，三 $1$ 个点。将一三，一二互相连边，再将二两两之间连边，这样度数增加 $1$，一二变成 $k$，三变成 $k-1$。最后将两个块的三连边就行 
### [CF553B](https://www.luogu.com.cn/problem/CF553B)
题意：略\
思路：

有一个结论：一个美丽排列一定是 $[1,2,3\dots n]$ 中，选择若干个不重复的长度为 $2$ 的小区间，然后翻转每个小区间。

考虑包含 $n$ 的那个循环，因为 $n$ 是最大值，所以 $n$ 的循环是所有循环的最后一个，并且 $n$ 位于这个循环的第一位。

- 如果长度为 $1$，显然成立

- 如果长度为 $2$，那么只能是 $[n,n-1]$

- 如果长度为 $3$，设循环为 $[n,x,y]$，有 $a_n=x,a_x=y,a_y=n$

- 如果 $x<y$ 那么原排列为 $[y,n,x]$
  - 如果 $x>y$ 那么原排列为 $[n,y,x]$

**不成立**

- 如果长度 $>3$，那么也不成立

设长度为 $n$ 的美丽排列数为 $f_n$

- $n=1,f_n=1$
- $n=2,f_n=2$
- $n>2,f_n=f_{n-1}+f_{n-2}$，代表前两项可以变或不变。

是斐波那契数列，然后通过递归得到答案，看这一位换不换
### [CF622D](https://www.luogu.com.cn/problem/CF622D)
题意：构造一个长度 $2n$ 的序列，$1$~$n$ 每个元素出现两次，定义 $d_i$ 为出现位置的差。使 $\sum_{i=1}^n(n-i)\times |d_i+i-n|$ 最小\
思路：只要这么构造 $1,3,5,\dots,5,3,1,2,4,6,\dots,4,2,$ 即可
### [CF1717D](https://www.luogu.com.cn/problem/CF1717D)
题意：一个高度为 $n$ 的满二叉树，初始在根节点，你最多能往右走 $k$ 次，问能走到多少个节点\
思路：枚举向右走多少步，那么答案就是$\sum_{i=0}^k C_n^i$
### [CF1918G](https://www.luogu.com.cn/problem/CF1918G)
题意：对于序列 $a$，定义 $b_i=a_{i-1}+a_{i+1},b_1=a_2,b_n=a_{n-1}$，求一个长度为 $n$ 的序列 $a$，使得 $a$ 与 $b$ 各个数出现次数相同\
思路：**经典**增量构造。设已经搞完了 $n-2$，$a$ 的最后两个是 $x,y$，新的是 $p,q$，那么 $b$ 的后四项就是 $b_{n-3},x+p,y+q,x$。显然 $x$ 与 $x$ 匹配，$p$ 与 $q+y$ 匹配，为了方便，让 $p+x$ 与 $y$ 匹配。这样解出来就是 $x=-q,y=p-q$，直接接上去就行
## 人类智慧
### [CF121C](https://www.luogu.com.cn/problem/CF121C)
题意：一个包含 $n$ 个数的排列，问排名为 $k$ 的排列有多少个位置和值都是由 $4,7$ 组成\
思路：由于 $k\le 10^9$，所以前面大部分都是不变的，直接搜索统计就行。后半部分使用逆康拓展开就可以
### [CF215D](https://www.luogu.com.cn/problem/CF215D)
题意：多个询问。每次有一个初始温度 $t$ 和忍耐温度 $T$，车上每多一个人温度增加 $1$，如果 $t>T$，要给车上每个人 $x$ 块钱，每辆车售价 $k$ 元，有 $n$ 位同学，问每个同学都上车需要的最小代价\
思路：只有两种情况，只买一辆车或者不交罚款买很多辆车，可以推式子证明不存在买几辆车再交罚款的情况。不交罚款要买 $\lceil \frac{n}{T-t} \rceil$ 辆车，所以要特判初始温度比忍耐温度高的情况
### [CF222D](https://www.luogu.com.cn/problem/CF222D)
题意：给定 $n$ 个人的两场考试成绩，不确定成绩是谁的。再给定一个人的最低成绩和，求这个人的最低排名与最高排名（按两场考试成绩和来排序\
思路：显然最高排名为 $1$，最低排名就让再他前面的人尽可能多，排个序然后最小的找最大的，不行就移动最小的就行
### [CF223B](https://www.luogu.com.cn/problem/CF223B)
题意：问 $s$ 每个位置都能和 $s$ 中一些其他位置组成 $t$，即 $t$ 作为 $s$ 的子序列，能将 $s$ 中每一个位置覆盖\
思路：顺序遍历 $s$，记录 $s$ 中每个数第一次在 $t$ 中第一次出现的位置，一个一个加的时候维护 $t$ 上的指针在哪里，同时不断地跳，最后指针要在最后一位上
### [CF226B](https://www.luogu.com.cn/problem/CF226B)
题意：可以进行若干次操作：将第 $i$ 堆石子合并到第 $j$ 堆石子上，代价为第 $i$ 堆石子大小。每堆石子只能被合并 $k$ 次，问所有石子合并到一堆的最小代价\
思路：显然从大到小排序，越靠前的数合并越小，相当于建一棵满 $k$ 叉树，相当于 $a_{k^{i-1}+1}$ 到 $a_{k^i}$ 要合并 $i$ 次，维护前缀和就行
### [CF362C](https://www.luogu.com.cn/problem/CF362C)
题意：你可以交换一对数，问有多少种情况使得交换后进行冒泡排序交换次数最多\
思路：枚举交换哪两个数，看一下交换完会影响哪些数，可以用一个 $s_{i,j}$ 代表前 $i$ 个数中 $\le j$ 的个数
### [CF372B](https://www.luogu.com.cn/problem/CF372B)
题意：多个询问，问一个矩形内有多少个全为 $0$ 的子矩阵\
思路：高维前缀和，$s_{i,j,l,r}$ 为左上角 $(i,j)$，右下角为 $(l,r)$ 的全为 $0$ 的子矩阵个数
### [CF420C](https://www.luogu.com.cn/problem/CF420C)
题意：每个人都支持两个人，求有多少对人 $(x,y)$ 使得有 $k$ 个人支持其中至少一个人\
思路：开一个桶记录每个人的被支持数 $a_i$，排序后发现对于一个人 $i$ 寻找第一个 $j$ 使得 $a_i+a_j \ge k$，但是这样会有重复的，比如一个人都支持选出的两个人，那么会重复，所以开一个map去重
### [CF448C](https://www.luogu.com.cn/problem/CF448C)
题意：$n$ 个木板每次可以竖着染一个木板或横着染所有木板一个（中途不能断掉）\
思路：如果横着染就要至少染到最小的，所以分治解决，每次找到最小的将当前区间分成两半
### [CF535D](https://www.luogu.com.cn/problem/CF529B)
题意：你可以交换不超过 $\lfloor \frac{n}2 \rfloor$ 次的 $a_i,b_i$，最后想让 $\min(b_1,b_2\dots b_n)\times \sum a_i$ 最小\
思路：枚举 $\min(b_1,b_2\dots b_n)=h$，如果 $a_i>h,b_i>h$ 那么这个 $h$ 不行；如果 $a_i > h,b_i \le h$，交换没有意义；如果n数，看一下交换完会影响哪些数，可以用一个 $s_{i,j}$ 代表前 $i$ 个数中 $\le j$ 的个数
### [CF372B](https://www.luogu.com.cn/problem/CF372B)
题意：多个询问，问一个矩形内有多少个全为 $0$ 的子矩阵\
思路：高维前缀和，$s_{i,j,l,r}$ 为左上角 $(i,j)$，右下角为 $(l,r)$ 的全为 $0$ 的子矩阵个数
### [CF420C](https://www.luogu.com.cn/problem/CF420C)
题意：每个人都支持两个人，求有多少对人 $(x,y)$ 使得有 $k$ 个人支持其中至少一个人\
思路：开一个桶记录每个人的被支持数 $a_i$，排序后发现对于一个人 $i$ 寻找第一个 $j$ 使得 $a_i+a_j \ge k$，但是这样会有重复的，比如一个人都支持选出的两个人，那么会重复，所以开一个map去重
### [CF448C](https://www.luogu.com.cn/problem/CF448C)
题意：$n$ 个木板每次可以竖着染一个木板或横着染所有木板一个（中途不能断掉）\
思路：如果横着染就要至少染到最小的，所以分治解决，每次找到最小的将当前区间分成两半
### [CF496D](https://www.luogu.com.cn/problem/CF496D)
题意：一个一局输赢序列，当一个人拿了 $t$ 分，那么他拿下这一场，当一个人赢了 $s$ 场，那么他赢了这一局，此时后面应该没有输赢了。问所有可能的 $s,t$\
思路：枚举一个 $t$ 那么 $s$ 是确定的，每次用二分跳 $t$ 场，如果最后跳到结尾时正好有人赢了 $t$ 次且这个人赢得比另外一个人多，那么这是一个合法的。二分跳多少可以用两个前缀和，这样就可以查询正好赢 $t$ 场了
### [CF524C](https://www.luogu.com.cn/problem/CF524C)
题意：若干种纸币，多次询问一个面值，问用最少的 $\le 2$ 种纸币凑出的张数\
思路：先用 $mp_i$ 表示用最少的一种纸币凑出 $i$ 的张数。枚举一种面值、再枚举选多少，另外一个直接在 $mp$ 里面查，加起来比个最小值
### [CF535D](https://www.luogu.com.cn/problem/CF529B)
题意：你可以交换不超过 $\lfloor \frac{n}2 \rfloor$ 次的 $a_i,b_i$，最后想让 $\min(b_1,b_2\dots b_n)\times \sum a_i$ 最小\
思路：枚举 $\min(b_1,b_2\dots b_n)=h$，如果 $a_i>h,b_i>h$ 那么这个 $h$ 不行；如果 $a_i > h,b_i \le h$，交换没有意义；如果 $a_i \le h,b_i >h$，那么一定要换；如果 $a_i \le h,b_i \le h,a_i>b_i$，在还有次数时可以换，记录一下，最后按 $a_i-b_i$ 排序即可。然后统计答案直接用最初的 $\sum a_i$ 加上每次变换的 $b_p-a_p$ 即可
### [CF552C](https://www.luogu.com.cn/problem/CF552C)
题意：一个天平，$101$ 个砝码 $k^0,k^1\dots,k^{100}$，左右都可以放，问能不能称出重量为 $n$ 的物体\
思路：如果 $n,n+1,n-1$ 都不是 $k$ 的倍数，那么肯定不行，否则就除以 $k$ 相当于缩减了一次。$n,n+1,n-1$ 相当于不放，放左边，放右边
### [CF613B](https://www.luogu.com.cn/problem/CF613B)
题意：每个人有一个技能上限，你有一些技能点，最后的战力是达到上限的人数 $\times c_1$ 加上最低的等级 $\times c_2$\
思路：枚举满级人数，二分最低等级，再二分最低等级人数
### [CF650B](https://www.luogu.com.cn/problem/CF650B)
题意：一个环，初始在 $1$，每次选择可以往左或右，都需要 $x$ 块，每到一个新的位置，如果是w，需要 $y+1$ 块，否则需要 $1$ 元。求有 $k$ 块钱情况下访问的最多不同位置数\
思路：二分答案，然后枚举环左边选多少个，用前缀和统计，因为左边右边都要走，所以有一边要走两遍，再看是左边快还是右边快，最后看这个代价是否 $\le k$
### [CF653C](https://www.luogu.com.cn/problem/CF653C)
题意：问交换一次情况下原序列变成一个波浪形的方案数\
思路：首先记录不合法的位置 $p$，如果 $>4$ 那么不行。否则枚举 $p_1$ 和 $p_1+1$ 与哪些位置交换 
### [CF1271E](https://www.luogu.com.cn/problem/CF1271E)
题意：
定义函数 $f(x)$ 如下：
$$
f(x) = \begin{cases}
\frac{x}{2} & \text{如果 } x \text{ 是偶数} \\
x - 1 & \text{否则}
\end{cases}
$$
找到最大的 $y$，使得
$$
\left \{ x \mid 1 \le x \le n,\, y \in path(x) \} \right| \ge k
$$
思路：发现 $x$ 是偶数时，$x,x+1,2x,2x+1,2x+2,2x+3,4x,4x+1,4x+2,4x+3,4x+4,4x+5,4x+6,4x+7$ 是合法的；$x$ 是奇数时，$x,2x,2x+1,4x,4x+1,4x+2,4x+3$ 是合法的。奇偶分开二分就行
### [CF1738D](https://www.luogu.com.cn/problem/CF1738D)
题意：一个排列 $a$ 和 $k$
- 如果 $a_i \le k$，找一个 $j\le i,a_j\ge k$ 且 $i-j$ 最小，$b_{a_i}=a_j$，否则 $b_{a_i}=n+1$
- 如果 $a_i > k$，找一个 $j\le i,a_j\le k$ 且 $i-j$ 最小，$b_{a_i}=a_j$，否则 $b_{a_i}=0$

给定 $b$，求满足条件的一组 $a,k$\
思路：若 $b_i > k$，则 $i \le k$；若 $b_i \le k$，则 $i>k$。\
所以 $k\in \left [\min(i,b_i),max(i,b_i)+1\right ]$\
解出 $k$ 之后由 $b_i$ 连向 $i$，$n+1$ 和 $0$ 只能出现一个，用这个为根，是一个树，优先遍历叶子节点
### [CF1462E2](https://www.luogu.com.cn/problem/CF1462E2)
题意：多少个子序列，长度为 $m$，极差 $\le k$\
思路：先排序，枚举一个最小值 $a_i$，二分一个最后满足 $a_j-a_i\le k$ 的 $a_j$，那么贡献是 $C_{j-i}^{m-1}$，因为确定选 $a_i$，加和就行
### [CF1739D](https://www.luogu.com.cn/problem/CF1739D)
题意：可以把 $u$ 与父亲的边删去，把 $u$ 和 $1$ 连边，问最大深度最小值\
思路：二分答案，从下往上看超过当前结果就接到 $1$ 上面
### [CF1747D](https://www.luogu.com.cn/problem/CF1747D)
题意：给定 $[l,r]$，每次选择 $l \le L \le R \le r$，满足 $R-L+1$ 是奇数，将 $a_L,a_{L+1},\dots,a_R$ 变成 $a_l,a_{L+1},\dots,a_R$ 的异或和。求最小操作次数使 $a_l,a_{l+1},\dots a_r$ 全变成 $0$\
思路：
- 如果 $a_l,a_l+1\dots a_r$ 异或和不为 $0$，那么肯定不行
- 如果全为 $0$，答案为 $0$
- 如果 $a_l=0$ 或 $a_r=0$ 或 $r-l+1$ 为奇数，那么答案为 $1$
- 再看有没有一段以 $l$ 为开头的前缀异或和为 $0$，有就为 $2$，可以通过map记录
- 否则为 $-1$
### [CF1777D](https://www.luogu.com.cn/problem/CF1777D)
题意：一棵树，你可以给每个节点分配 $0/1$，分配完之后进行若干轮循环，每次 $u$ 的权值变成所有子节点异或之和，直到全为 $0$，这次分配的价值为每次循环之后的和。求所有的分配方式价值之和\
思路：经过 $i$ 轮操作后，第 $u$ 个点的权值会变成 $u$ 下面 $i$ 层节点异或之和，当一层异或值为 $1$ 时，需要奇数个 $1$，恰好占总情况数的一半，所以直接把答案乘以 $2^{n-1}$。
### [CF1861D](https://www.luogu.com.cn/problem/CF1861D)
题意：每次操作可以将一段区间乘以一个整数，问使这个序列单调增加的最小操作次数\
思路：将序列分成两个部分，一半乘负数，一半正数，前缀和处理连续上升和下降子串个数
### [CF1965C](https://www.luogu.com.cn/problem/CF1965C)
题意：一个 $01$ 纸条，可以在两数之间折叠，前提是折叠部分完全相等，问纸条若干次折叠后最短的长度\
思路：从左往右考虑，每遇到两个相邻且相同的字符就翻转一次。这样一定合法且最优。维护当前方案，有相同的就换一个方向，同时维护当前位置，记录一下最小值与最大值
### [CF1984C2](https://www.luogu.com.cn/problem/CF1984C2)
题意：给定一个变量 $c=0$，对于每个 $a_i$，选择 $c=c+a_i$ 或 $c=|c+a_i|$，问凑成最大值的方案数\
思路：记录一下前缀和，如果前缀和最小值为负数，那么肯定要在那个位置取绝对值，并且前面的负不取，因为当前目标是尽可能的负。如果前缀为正，两种都可以，记录这种个数为 $p$，每遇到一个最小值，贡献就是 $2^{n-i+p}$，代表后面能随便选，前面部分选（翻了之后后面都是正数）
### [CF2013E](https://www.luogu.com.cn/problem/CF2013E)
题意：将一个序列重新排列后，求 $\min \sum_{i=1}^n \gcd(a_1,a_2\dots,a_i)$\
思路：结论题，把最小的 $a_i$ 放在最前面，然后每次取 $\gcd$ 最小的那个。
$$若a<b,则 a+\gcd(a,b)\le b$$
证明：$\gcd(a,b)=\gcd(b-a,a)=\gcd(a-(b-a),b-a)=\gcd(b,b-a)\le b-a$，所以 $a+\gcd(a,b)\le a+(b-a)\le b$

证明结论：
![](https://cdn.luogu.com.cn/upload/image_hosting/m5txipze.png)
首先：${\color{Blue} 1+2+3} \ge {\color{Red} 1+2+3}$，因为红前面多了一个数\
蓝：$b+{\color{Blue} 1+2+3+4}\ge b+{\color{Blue} 1+2+3}+1 $\
红：$a+\gcd(a,b)+{\color{Red} 1+2+3}=b+{\color{Red} 1+2+3}\le b+{\color{Blue} 1+2+3}+1$\
所以：红 $<$ 蓝。其他同理可证
## 前后缀和与查分
### [P1360](https://www.luogu.com.cn/problem/P1360)
题意：每天都提升若干个能力，求最长的一段区间，使得这个区间内每种能力提升次数相等\
思路：前缀和统计，可以用每个数与第一项能力的差值来哈希记录，如果相等说明是合法区间
## 数据结构优化
### [P5025](https://www.luogu.com.cn/problem/P5025)
题意：每个炸弹有一个位置和一个爆炸范围，求每个炸弹能引爆多少炸弹\
思路：先更新左边界与最大炸的范围，然后在更新右边界的同时计算先炸掉右边一个大的引爆左边的情况
### [CF359C](https://www.luogu.com.cn/problem/CF359C)
题意：求 $\frac{1}{x^{a_1}}+\frac{1}{x^{a_2}}+\dots \frac{1}{x^{a_n}}$ 的分母与分子的 $\gcd$\
思路：观察通分过程，答案为 $\min(sum-a_i)$，但是可能会有重复的比如 $12\times 2^2=3\times 2^4$，所以开一个优先队列从小到大不断合并就行
### [CF367B](https://www.luogu.com.cn/problem/CF367B)
题意：给定两个序列，问 $a$ 中有多少个位置 $q$ 使得 $a_q,a_{q+p},a_{q+2p}\dots a_{q+(m-1)p}$ 与 $b$ 中各个数出现次数相等\
思路：显然对于一个 $q1=ap+x,q2=(a+1)p+x$，它们的序列是差不多的，所以根据 $q$ 模 $p$ 的余数分组，依次处理每组，每一组有 $\frac{n}i$ 个，一共有 $i$ 组。对于每一组，开一个队列，当长度达到 $m$ 时就把队头踢了，同时开一个map维护桶就行 
### [CF377B](https://www.luogu.com.cn/problem/CF377B)
题意：有若干个问题和若干个人，每个人每天可以解决一个难度 $\le$ 自己能力值的题，前提是你雇佣了他。求一种问题解决方式，使得花费钱数不超过你拥有的并且总的完成天数最小\
思路：题目按难度排序，人按能力排序。然后二分完成天数 $x$，对于每个问题，把能力值大于难度都扔进优先队列里（按钱数花费排序），然后让花费最小的人做 $x$ 道题，最后看花费是否满足与每个问题有没有解决即可
### [CF547B](https://www.luogu.com.cn/problem/CF547B)
题意：定义一个区间价值为其最小值，对于每个 $i$，求所有长为 $i$ 的区间价值的最大值\
思路：对于一个 $i$，用单调栈维护出左右边最后一个 $\le a_i$ 的位置 $l,r$，那么 $[l,r]$ 的最小值就为 $a_i$，长度在 $[1,r-l+1]$ 的区间答案就可以用 $a_i$。统计答案可以只更新 $ans_{r-l+1}$，最后 $ans_i=\max(ans_i,ans_{i+1})$ 
### [CF557C](https://www.luogu.com.cn/problem/CF557C)
题意：一张桌子，$n$ 条腿，每条腿有一个长度和价值，现在要拿掉若干条腿，假设还剩下 $k$ 条腿，那么长度最长的腿数量要 $> \lfloor \frac{k}2 \rfloor$，要使移除的价值和最小\
思路：要最小化拿走的价值，即最大化剩下的价值。\
枚举超过一半的那条腿的长度，假设有 $len$ 个这种长度的，要使移除的价值最小，那么肯定要尽可能的多拿价值大的腿，用 multiset 维护最大值，尽可能选 $len-1$ 个，然后拿所有价值和减去选出来的更新答案就行
### [CF1847D](https://www.luogu.com.cn/problem/CF1847D)
题意：一个01序列，给定 $m$ 个区间 $l_i,r_i$，把 按$l_1,l_1+1\dots r_1,l_2,l_2+1\dots r_2$ 的顺序构造出一个序列，多个操作，每次将一个位置取反，问使序列最大所需要的最小交换次数（不影响后面的询问）\
思路：显然每个位置有一个重要值，维护每个数在构造序列里第一次出现的位置，可以用线段树倒着赋值。发现一定是有先给靠前的数赋 $1$，设 $x=\min(总共的1，有用的位置)$，那答案就是前 $x$ 个里面有几个 $0$，拿树状数组维护
# 数据结构
## 并查集
### [CF566D](https://www.luogu.com.cn/problem/CF566D)
题意：最开始每个数都位于自己的集合。三种操作，合并两个数所在集合、合并一段区间内的所有数所在集合、查询两个数是否属于一个集合\
思路：有点像[这道题](https://www.luogu.com.cn/problem/P2391])，发现合并区间时有很多的重复（即合并的数已经在一个集合）。记录每个数右边第一个和它不在一个集合的位置 $p_i$，合并一段区间时直接跳 $p_i$ 即可，跳过的部分都和 $i$ 在一个集合内，所以不用在合并了。\
初始化将 $p_i$ 设为 $i+1$ 即可。
## 莫队
### [P3604](https://www.luogu.com.cn/problem/P3604)
题意：多个询问，每个询问求 $[l,r]$ 区间内重排后是回文串的子串个数\
思路：一个区间重拍后是回文串的条件是只有一个或没有字母出现次数为奇数。所以状态压缩，然后前缀异或一下，$1$ 代表出现次数为奇数，$0$ 代表偶数。\
题意转化为选择 $[l-1,r]$ 的两个不同位置后将前缀异或的值异或一下，使得到的值为 $0$ 或 $2^k$ 的方案数。\
莫队每加入或删除一个数之后，查询有多少个前缀异或值和其相等或者只差一位
### [P3674](https://www.luogu.com.cn/problem/P3674)
题意：多个询问，每次询问一个区间内有没有两个数（可以重复）的和或差或积为 $x$\
思路：用bitset维护区间内哪些数出现过，$c$ 正着，$d$ 反着。查询差时看 $c$ & $c<<x$ 是否为 $0$，查询和时看 $c$ & $d>>(M-x)$，查询积时枚举因数在 $c$ 里面查就行
### [P4396](https://www.luogu.com.cn/problem/P4396)
题意：多个询问，查询 $[l,r]$ 内有多少数（可以重复）在 $[a,b]$ 内与有多少个不同数在 $[a,b]$ 内\
思路：插入与删除时在桶上操作。查询用分块，维护这个数出现次数，每个块内数的个数，每个块内实际个数。把 $[a,b]$ 拆成整块和散块来看
### [P4462](https://www.luogu.com.cn/problem/P4462)
题意：多个询问，求 $[l,r]$ 内有多少个子序列异或和为 $k$,所有询问共用一个 $k$\
思路：前缀异或一下，然后开桶记录前缀异或值出现次数，相当于在 $[l-1,r]$ 内选两个数异或值为 $k$，新加入一个数就把 ${s_i}\oplus k$ 的个数加到答案里
### [P4867](https://www.luogu.com.cn/problem/P4867)
题意：多个询问，查询 $[l,r]$ 内有多少个不同数在 $[a,b]$ 内\
思路：与 [P4396](https://www.luogu.com.cn/problem/P4396) 相似，莫队+值域分块
### [P4688](https://www.luogu.com.cn/problem/P4688)
题意：每次询问三个区间内每个数出现次数最小值之和\
思路：可以把区间拆开，但是这题需要维护每个数出现次数，所以说提前给每个数分配好空间，就是它在排序后数组的下标加上出现次数，这样用bitset维护就行，最后把三个bitset与一下就行。但这题卡空间，每次少处理几个询问，分多次处理就行
## STL
### [P1110](https://www.luogu.com.cn/problem/P1110)
题意：初始 $n$ 个块，每次往一个块后插入一个数、求所有数两两之间的最小值、相邻两数的绝对值\
思路:开两个multiset，一个维护所有数差值，一个维护相邻数的差值。并且维护每个块开头和结尾的数，插入一个数时更新它和当前块最后一个数和下一个块的开头；删除当前块结尾和下一块开头的差，加入它和上一个数、下一个数的差
## 线段树
### [P6348](https://www.luogu.com.cn/problem/P6348)
题意：一个区间向另一个区间建图，求最短路\
思路：一个区间向一个虚点 $u$ 连 $0$，$u$ 向虚点 $v$ 建边权为 $1$.然后 $v$ 向另一个区间连 $0$，注意空间 $4*2+1=9$ 倍
### [CF786B](https://www.luogu.com.cn/problem/CF786B)
题意：区间向点建图或者反过来，求最短路\
思路：线段树优化，一个区间看成一个点，建两个树
# 图论
## 树上问题
### [P3066](https://www.luogu.com.cn/problem/P3066)
题意：询问每个点的子树中有多少个点到这个点距离 $\leq k$\
思路：考虑每个点的贡献，一定是对连续的一段祖先产生，所以记录每个点的 $2^i$ 级祖先，然后倍增找能贡献到哪里，然后树上查分修改
### [P4281](https://www.luogu.com.cn/problem/P4281)
题意：求一个点，使得三个给定的点到这个点距离之和最短\
思路：显然为深度最低的 $lca$，然后统计答案
### [CF685B](https://www.luogu.com.cn/problem/CF685B)
题意：查询若干个点的重心\
思路：先搜索一遍，对于一个点，它的重心在重儿子的重心父亲辈上，在更优情况下不停移动就行
### [CF1976F](https://www.luogu.com.cn/problem/CF1976F)
题意：一棵树，$1$ 只有一个儿子，要加 $k$ 条边，可以重边。要求对每条割边，它的在树上深度较大的节点的子树内所有树边也都是割边，并且割边数最少，输出加 $i$ 条边后树上割边的最小值\
思路：显然第一次要根一个叶子节点连边，如果连其他的话 $1->u$ 作为一个割边它的下面不是割边就非法了，而且一定是与最深的连边，这样剩下的割边最小。而后面就是找两条不在环上长度最长的两条链（在红链两边），把叶子节点连一起。
![](https://cdn.luogu.com.cn/upload/image_hosting/3v1l71po.png)
每次把两条蓝链变成红链，然后就类似长链剖分了，每条链的贡献就是到链顶的长度，把这个扔到优先队列里面，然后不停减就行
## 并查集
### [P1197](https://www.luogu.com.cn/problem/P1197)
题意：每次删去一个点，然后问图中的连通块个数\
思路：反过来变为建图，注意一条边的建图顺序取决于连接的两个点中更靠前被摧毁的
## 最小生成树
### [P10928](https://www.luogu.com.cn/problem/P10928)
题意：一个树，增加几条边为完全图，使最小生成树为原树，问增加边权最小值\
思路：模拟最小生成树过程，合并两个集合时，加的权值为这条边权值$+1$
### [CF472D](https://www.luogu.com.cn/problem/CF472D)
题意：给出一个树上结点两两之间距离，还原这棵树\
思路；这棵树一定是最小生成树，因为长度越小的距离越有可能是树上真实的边。直接跑一遍，然后跑一遍搜索检查就行
## 最短路
### [P2886](https://www.luogu.com.cn/problem/P2886)
题意：一张无向图，求起点到终点恰好经过 $k$ 条边的最短路长度\
思路：用min矩阵来模拟floyd走一步，快速幂加速
### [P10927](https://www.luogu.com.cn/problem/P10927)
题意：最小环的权值和\
思路：floyd更新前取答案
### [CF208C](https://www.luogu.com.cn/problem/CF208C)
题意：找一个点，经过这个点的边为特殊边，设价值为 $\frac{1到n所有最短路中包含特殊边的个数}{1到n的最短路条数}$，求价值最大值\
思路：枚举那个点，显然如果这个点不为 $1$ 或 $n$，那么特殊边就为 $1$ 个，预处理最短路 $d$ 与最短路径数 $c$，如果 $d_{1,i}+d_{i,n}=d_{1,n}$ 那么包含的特殊边个数即为 $2\times c_{1,i}\times c_{i,n}$，取最大即可
### [CF1998D](https://www.luogu.com.cn/problem/CF1998D)
题意：两个人A和B，两种边 $i$ 到 $i+1$ 与 $u_i$ 到 $v_i(u_i < v_i)$，A可以走两种边，B只能走第二种边。只要一个人走过一个点，另外一个人就不能走了。现在进行 $n-1$ 轮游戏，第 $i$ 轮A从 $1$ 开始，B从 $i$ 开始，B先走，问谁先到\
思路：A只要走到B前面就行，B开始点移动时，相当于A可以多用一个点来快速跳。设 $d_i$ 为到达 $i$ 的最短时间，每多一个点就更新 $d$，同时记录 $res=\min(n-i+d_i)$，最后看 $res$ 和 $n-i$ 大小
## Tarjan
### [B3609](https://www.luogu.com.cn/problem/B3609)
题意：求强连通\
思路：Tarjan模板题
### [P1073](https://www.luogu.com.cn/problem/P1073)
题意：求一条路径，使路径上的点最大值-最小值最大\
思路：缩点后，按拓扑序记录最小值，然后按这个点的最大值更新
### [P1262](https://www.luogu.com.cn/problem/P1262)
题意：你可以通过贿赂一个人，来知道他所在强连通里所有人的信息。问知道所有人信息需要的最少钱。\
思路：缩点后，答案即为所欲入度为0的强连通里的最少钱
### [P1407](https://www.luogu.com.cn/problem/P1407)
题意：给你一些夫妻关系和初恋关系，如果一对夫妻关系破裂后，每个人都能找到初恋，然后初恋的夫妇还能找到初恋……以此类推形成一个环，那么这对婚姻是不安全的，否则不安全\
思路：将夫妻为男连女，初恋为女连男。然后Tarjan看夫妻是不是在一个强连通里
### [P1653](https://www.luogu.com.cn/problem/P1653)
题意：每个点向所有比它低的点连有向边，问还需连多少条无向边才能使整张图连通\
思路：先建图跑缩点，统计入度为 $0$ 的强连通与出度为 $0$ 的强连通数量 $x,y$ 然后输出 $max(x,y)$。感性理解：先一直走，走到走不动了，连向一个无法进入的点，以此类推，最后把剩下的没有出度或没有入度的点连到现在的环上
### [P2194](https://www.luogu.com.cn/problem/P2194)
题意：消掉一个强连通的代价为其中最小的权值。问消掉整张图的最小代价与方案数\
思路：记录最小值与最小值的个数，然后乘法原理
### [P2746](https://www.luogu.com.cn/problem/P2746) 
题意：求入度为0的连通块个数与使整张图为强连通\
思路：统计完入度为0与出度为0的个数后取max即可
### [P2860](https://www.luogu.com.cn/problem/P2860)
题意：使无向图上每个点都在环上\
思路：缩边双后的树，统计度数为1个数 $x$，答案即为 $(x+1)/2$
### [P3469](https://www.luogu.com.cn/problem/P3469)
题意：统计每个节点去掉后，不连通点对个数\
思路：不是割点显然为 $2(n-1)$，去掉一个割点即 $2(n-1)+\sum_{i=1}^k \sum_{j=1,j\neq i}^{k}size_i \times size_j$，优化$\sum_{j=1,j\neq i}^k size_j =n-size_i-1$。最后加上剩下的点
### [P4630](https://www.luogu.com.cn/problem/P4630)
题意：给定一张简单无向图，问有多少对三元组 $\langle s, c, f \rangle$（$s, c, f$ 互不相同）使得存在一条简单路径从 $s$ 出发，经过 $c$ 到达 $f$\
思路：对原图建出圆方树后，两点之间简单路径的点数，就和它们在圆方树上路径经过的方点（点双）和圆点的个数有关。本题中，每个方点的权值为对应点双的大小，而每个圆点权值为 $-1$，这样赋权后则有两圆点间圆方树上路径点权和，恰好等于原图中简单路径并集大小减 $2$。所以，考虑每个点对答案贡献，为权值乘以经过此点路径数，DP即可
### [P10935](https://www.luogu.com.cn/problem/P10935)
题意：告你若干个不等式，求所有数的和的最小值\
思路：由于SPFA会卡，又因为权值只有0或1用Tarjan来看，设 $dp_i$ 代表从点 $ i$ 的前驱转移到点 $i$ 的最长路径是多少，则动态转移方程就是 $dp_i=max(dp_i,dp_j+dis)$。答案即为$\sum_{i=1}^{len} s_i \times dp_i$
### [P10944](https://www.luogu.com.cn/problem/P10944)
题意：一个图中任意两点 $u,v$ 是否都满足 $u$ 到达 $v$ 或 $v$ 到达 $u$ \
思路：Tarjan缩点，必须为一个链才合法，入度为 $0$ 的和出度为 $0$ 的点都只有 $1$ 个 
### [abc395_e](https://www.luogu.com.cn/problem/AT_abc395_e)
题意：可以花费代价翻转一些有向边，问最短路\
思路：分层图，翻转边看成建额外代价的虚边
## 2-SAT
### [P10969](https://www.luogu.com.cn/problem/P10969) 
题意：告诉你若干组 $$X_a \ \text{op} \ X_b = c$$，求是否有数组 $01$ 数组 $X$\
思路：2-SAT，建图后Tarjan判断
### [CF228E](https://www.luogu.com.cn/problem/CF228E)
题意：一个图，边权为 $0$ 或 $1$，每次修改一个点时，会把这个点连得边边权异或 $1$，给出一个方案使所有边权为 $0$\
思路：显然每个点要么变 $1$ 次，要么不变。对于一个边权为 $0$ 的边，那么 $u,v$ 要么都变要么都不变；如果边权为 $1$ 的边，那么 $u,v$ 只能有一个变。是一个 2-SAT 问题
## 二分图匹配
### [P5089](https://www.luogu.com.cn/problem/P5089)
题意：一个网格中，有 $3$ 个在网格上的点并且在一个矩形的三个角上，那么可以构造出另一个角，问把这个网格填满最少要添加几个点\
思路：建立二分图，行为左边、列为右边，转化成求连通块个数
### [P10937](https://www.luogu.com.cn/problem/P10937)
题意：一个网格上一些点不能放，问最多能放多少个車\
思路：每个車占领一行与一列，所有二分图左边为行，右边为列，除了占领的点两两之间有边，跑二分图最大匹配
## 欧拉路
### [P6066](https://www.luogu.com.cn/problem/P6066)
题意：是否存在一条路径使得经过每条无向边恰好两遍\
思路：直接dfs搜索
### [CF788B](https://www.luogu.com.cn/problem/CF788B)
题意：总共有 $n$ 个节点，$m$ 条路径，要求其中 $m-2$ 条路径走两遍，剩下 $2$ 条路径仅走一遍，问不同的路径总数有多少，如果仅走一遍的两条边不同则将这两条路径视为不同\
思路：将一条边拆成两个，问题转化成删去两条不一样的边后，成为一个无向欧拉图的情况数。无向欧拉图的判定是所有点度数为偶数或只有两个点度数为奇数，删去一个自环后所有点奇偶性不变，设有 $k$ 个自环，贡献为 $C_k^2+k\times (m-k)$，可以选择删去两个自环或者删一个自环和一个正常边，还可以删去同一个点的两条边，贡献是 $\sum d[u]$。还需要特判整张图不连通，此情况答案为 $0$
# 字符串
## 字典树
### [CF633C](https://www.luogu.com.cn/problem/CF633C)
题意：给定一个字符串和若干个单词，给出一种方式使得，字符串由若干个单词反转拼接而成的\
思路：先将倒置的单词扔到Trie上，再将字符串倒置后从前往后遍历，设 $f_i$ 为 $s_{0\dots i}$ 合法拼接而成所用的最后一个单词，对于每个 $i$，寻找一个 $j\le i$ 使得 $s_{j\dots i}$ 是一个单词，那么更新 $f$ 的同时，记录一下从哪转移而来的就行。最后输出方案
### [CF1983F](https://www.luogu.com.cn/problem/CF1983F)
题意：定义一个区间价值为 $\min(a_i\otimes a_j)$，求所有区间价值的第 $k$ 小\
思路：显然可以二分答案 $val$，相当于求最小的 $val$ 使得权值 $\le val$ 的区间 $\ge k$。枚举一个右端点，要找一个最大的 $l$ 使得 $a_l \otimes a_r\le val$。扔到字典树上，如果 $val$ 这一位为 $1$ 那么和 $a_r$ 这一位相同的可以贡献，往另一边走；如果 $val$ 这一位为 $0$ 那么只能走与 $a$ 一位相同的，贡献就是 $\log n$ 个子树拼一块，取 $\max$，需要和之前 $r$ 的 $l$ 取 $\max$，$\le val$ 的个数即为 $\sum l$
## 哈希
### [P3667](https://www.luogu.com.cn/problem/P3667)
题意：求最短区间 $l,r$ 使 $n$ 个字符串的 $l,r$ 与另 $n$ 个不重合\
思路：二分答案，然后哈希检查
### [P4407](https://www.luogu.com.cn/problem/P4407)
题意：给定一些文本串和模式串。对于每个模式串 $s$，看有多少个文本串可以由 $s$ 删除一个字母、添加一个字母、修改一个字母变成\
思路：记录每个模式串前缀与后缀哈希值。删除相当于两段拼，添加相当于多一个字母，修改直接加/减，然后再去文本串里查即可
## 回文自动机
### [P4287](https://www.luogu.com.cn/problem/P4287)
题意：定义一个双倍回文子串为能长度是 $4$ 的倍数且前半部分和后半部分都是回文串。求最长双倍回文子串长度\
思路1：马拉车更新时，从 $i$ 往后看\
思路2：回文自动机定义 $trans$ 指针为长度不超过原串一半的最长回文后缀，从父亲的 $trans$ 开始跳。当 $trans[i]$ 的长度恰好为 $i$ 的一半时并且为偶数时统计答案
## 马拉车
### [P4555](https://www.luogu.com.cn/problem/P4555)
题意：求一个最长子串 $T$，使 $T$ 能分成两个回文子串\
思路：马拉车同时记录以 $i$ 为开头/结尾的最长回文串的长度，更新 $p_i$ 时更新 $r[i+p[i]-1]=max(r[i+p[i]-1],p[i]-1)$，最后由于每次只是更新最长的所以要缩一下
## KMP
### [P3435](https://www.luogu.com.cn/problem/P3435)
题意：对于每个 $s$ 的前缀，求最长的真前缀 $t$ 使得 $s$ 是 $t$ 的前缀\
思路：相当于求最短的 $border$，设 $dp_i$ 为 $[1,i]$ 的最短，则 $dp_i=\min(dp_i,dp_{pi_i})(pi_i\ne 0)$，答案为 $\sum dp_i(dp_i \ne 0)$
### [P4391](https://www.luogu.com.cn/problem/P4391)
题意：求最小循环节\
思路：为 $n-ph_n$，可以通过定义理解，相当于一段一段相等
### [CF535D](https://www.luogu.com.cn/problem/CF535D)
题意：给定一个模式串在文本串出现的位置，问文本串的可能数\
思路：如果文本串有 $x$ 个数没有被覆盖那么答案为 $26^x$。对于两个位置，如果重叠，发现合法情况就是 $i=len$ 开始，每次 $i=pi_i$ 的 $i$。判完合法就看有几个位置没有被覆盖掉
# 数学
## 推式子
### [P1390](https://www.luogu.com.cn/problem/P1390)
题意：给定 $n$，求$$\sum_{i = 1}^n \sum_{j = i + 1}^n \gcd(i, j)$$\
思路：设 $f[k]$ 代表 $gcd(i,j)=k$ 的个数，$g[k]$ 代表 $gcd(i,j)%k=0$ 的个数，则 $g[k]=(\frac{n}{k})^2$ 并且 $g[k]=f[k]+f[2k]+f[3k]+f[4k]...$ 然后移项得 $f[k]=g[k]-f[2k]-f[3k]-f[4k]...$ 倒序处理即可
### [P2257](https://www.luogu.com.cn/problem/P2257)
题意：求有多少 $(x,y)$ 满足 $1 \le x \le a,1 \le y \le b$ 使 $\gcd(x,y)$ 为质数\
思路：根据P2522，可以想到枚举 $k$ 然后算贡献
$$\sum_{k=1}^{n} \sum_{x=1}^{\left \lfloor \frac{n}{k} \right \rfloor } \mu(x) \times \left \lfloor \frac{a}{kx} \right \rfloor \times \left \lfloor \frac{b}{kx} \right \rfloor $$
设 $T=kx$，则原始变为
$$\sum_{k=1}^{n} \sum_{x=1}^{\left \lfloor \frac{n}{k} \right \rfloor } \mu(x) \times \left \lfloor \frac{a}{T} \right \rfloor \times$$
将 $T$ 提到前面
$$\sum_{T=1}^{n}\left \lfloor \frac{a}{kx} \right \rfloor \times \left \lfloor \frac{b}{kx} \right \rfloor \sum_{k|T} \mu(\frac{T}{k})$$
后面这部分可以前缀和预处理，然后就是数论分块
### [P2522](https://www.luogu.com.cn/problem/P2522)
题意：多个询问，每个询问给定 $a,b,c,d,k$，问有多少数对 $(x,y)$ 满足 $a \le x \le b,c \le y \le d$ 使 $\gcd(x,y)=k$ \
思路：转化成简单问题 $ans(a,b)$，求有多少 $(x,y)$ 满足 $1 \le x \le a,1 \le y \le b$ 使 $\gcd(x,y)=k$，即
$$\sum_{i=1}^{a} \sum_{j=1}^{b} \left [\gcd(i,j)=k \right ] $$
$$\sum_{i=1}^{\left \lfloor \frac{a}{k}  \right \rfloor } \sum_{j=1}^{\left \lfloor \frac{b}{k}  \right \rfloor} \left [\gcd(i,j)=1 \right ] $$
$$\sum_{i=1}^{\left \lfloor \frac{a}{k}  \right \rfloor } \sum_{j=1}^{\left \lfloor \frac{b}{k}  \right \rfloor} \sum_{x|\gcd(i,j)} \mu(x)$$
$$\sum_{i=1}^{\left \lfloor \frac{a}{k}  \right \rfloor } \sum_{j=1}^{\left \lfloor \frac{b}{k}  \right \rfloor} \sum_{x=1} \mu(x) \times \left [ x|\gcd(i,j) \right ] $$
$$\sum_{x=1} \mu(x) \times \left \lfloor \frac{a}{xd} \right \rfloor \times \left \lfloor \frac{b}{xd} \right \rfloor $$
整除分块即可，预处理 $\mu(x)$ 前缀和，然后按类似二位前缀和的做：$ans(b,d)-ans(a-1,d)-ans(b,c-1)+ans(a-1,c-1)$
### [P3723](https://www.luogu.com.cn/problem/P3723)
题意：求 $\sum_{i=1}^n\left(a_i+x-b_i\right)^2$\
思路：展开后相当于求 $\sum_{i=1}^na_ib_i$ 最小值，把 $b$ 翻转一下，$a$ 复制一遍，这样卷一下，发现系数就是交叉的和，枚举加多少
### [P4980](https://www.luogu.com.cn/problem/P4980)
题意：将一个 $n$ 个点的环染色，有 $n$ 种颜色，问有多少种本质不同的方案数\
思路：
**Burnside**定理：
$$|X/G|=\dfrac{1}{|G|}\sum_{g\in G} X^g$$
可以旋转 $0,1,2,...n-1$ 次，设旋转后 $k$ 次，则那些点为 $i,i+k,i+2k...i+xk$，所以 $i\equiv i+xk\mod n$ 所以 $xk \equiv 0\mod n$，所以 $x$ 的最小值为 $\frac{n}{\gcd(n,k)}$，又因为不同起点不会公用（公用时两点模 $k$ 同余，但 $\gcd(n,k) \le k$），所以起点个数为 $\gcd(n,k)$ 个，贡献为 $n^{\gcd(n,k)}$，那么答案为 $\frac{1}n \sum_{k=1}^{n}n^{\gcd(n,k)}$  
### [CF223C](https://www.luogu.com.cn/problem/CF223C)
题意：求一个序列做 $k$ 遍前缀和后的样子\
思路：手推一下发现 $a_i=\sum_{j=1}^{i}a_jc_j$，系数即为杨辉三角形第 $k-1$ 行到 $k-1+n$ 行的 $k-1$ 列，即为 $C_{k-1+j}^{k-1}$，$C_i^j$ 拆一下式子为 $\frac{(j+1)\times(j+2)\dots\times i}{(i-j)!}$。由于 $k$ 很大，$n$ 比较小，所以预处理 $s_i=s_{i-1}\times (k+i)$ 和阶乘 $f_i=f_{i-1}\times i$，则 $C_n^k=\frac{s_{n-k}}{f_{n-k}}$，然后就处理每一个数就行
### [CF439E](https://www.luogu.com.cn/problem/CF439E)
题意：有多少个长度为 $m$，和为 $n$ 的序列，使得 $\gcd(a_1,a_2\dots a_n)=1$\
思路：设 $f(n)$ 为答案，$g(n)$ 为没有 $\gcd$ 限制方案数。最后 $\gcd$ 答案肯定是 $n$ 的约数，枚举 $\gcd=d$，$g(n)=\sum_{d|n}f(\frac{n}d)$，然后就是莫比乌斯反演，$f(n)=\sum_{d|n}g(d)\times \mu(\frac{n}d)$，$g(d)$ 可以用组合数快速算
### [CF535C](https://www.luogu.com.cn/problem/CF535C)
题意：一个首项为 $a$，公差为 $b$ 的等差序列，每次询问一个 $l$ ，查询一个最大的 $r$ 使得对于 $[l,r]$ 内，操作不超过 $t$ 次，每次选不超过 $m$ 个数 $-1$，使得 $[l,r]$ 都变成 $0$\
思路：二分，一个 $[l,r]$ 合法条件是和 $\le t\times m$ 与 $\max \le t$
### [CF599D](https://www.luogu.com.cn/problem/CF599D)
题意：求满足由 $x\times y$ 个小正方形构成的矩阵内恰好有 $n$ 个正方形的所有 $x,y$。\
思路：
小学奥数可得，一个 $i\times j$ 的矩形有 $ij+(i-1)(j-1)+(i-2)(j-2)+\dots+(i-i+1)(j-i)(i\le j)$ 个小正方形，式子的意义就是从小到大枚举小正方形的边长。

拆括号：$ij+ij-i-j+1+ij-2i-2j+4\dots +ij-i^2-ij+(i-1)^2$。

整理一下：$i^2j-\frac{i(i-1)}{2}(i+j)+\frac{i(i-1)(2i-1)}{6}=n$。

用 $i,n$ 表示 $j$：$j=\frac{2n-\frac{i(i-1)(2i-1)}{3}+i^3-i^2}{i^2+i}$。

枚举一下 $i$，然后就可以求得 $j$ 了，注意要满足$i\le j$，才能保证不重不漏，$i$ 的范围大概是 $\sqrt[3]{3n} $。
### [CF1332E](https://www.luogu.com.cn/problem/CF1332E)
题意：一个棋盘，每个格子放 $[l,r]$ 个方块，问有多少种方案使得每次往一个格子多放两个或者将两个有公共边的方块各放一个能使高度一样\
思路：设最后高度为 $k$，显然如果 $k$ 够大的话，并且要加的是偶数，那么一定可以。如果 $nm$ 是奇数，可以随便放，因为可以调整 $k$ 的奇偶；如果大小为偶数，那么初始有奇数个方块的格子必须有偶数个，这样和才为偶数，答案为 $\sum_{i=0,i\bmod 2=0}^{nm}x^iy^{nm-i}$，$x,y$ 为 $[l,r]$ 内奇数与偶数个数，有点像二项式定理，为 $\frac{(y+x)^{nm}+(y-x)^{nm}}2$（奇数项消掉了，偶数项重复了一次）
### [CF1744E2](https://www.luogu.com.cn/problem/CF1744E2)
题意：构造 $x,y$ 满足 $a < x \le c,b<y\le d$，$x \times y$ 是 $a \times b$ 的倍数\
思路：枚举 $a,b$ 的所有质因子，然后枚举 $x=$ 两个质因子相乘，那么 $y=\frac{a\times b}x$，然后把 $x,y$ 扩大到最大的 $c,d$ 范围后，看是否大于 $a,b$
### [CF1930F](https://www.luogu.com.cn/problem/CF1930F)
题意：每次添加一个数，求 $\max(\max(a_i|x)-\min(a_i|x))$，强制在线\
思路：考虑枚举 $\max=i,\min=j$，那么 $x$ 为 $a_i$ 的补集，只有 $a_i$ 的一位为 $1$ 且 $a_j$ 的那一位为 $0$ 才有贡献。设 $s_s$ 为是否存在 $s \subseteq a_i$，$t_s$ 为是否存在 $s \subseteq a_i的补集$，答案就为最大的 $s$ 满足 $s_s=t_s=1$，输入一个 $a_i$ 就暴力更新子集就行，每个 $s$ 最多更新一次，所以时间复杂度是 $O(n)$
## 计数
### [CF9D](https://www.luogu.com.cn/problem/CF9D)
题意：一棵大小为 $n$ 的二叉树，满足高度 $\ge k$ 的有多少个\
思路：$dp_{i,j}$ 代表高度 $\le i$ 大小为 $j$ 的二叉树个数。转移就枚举左子树大小 $k$，那么 $dp_{i,j}=dp_{i-1,k}\times dp_{i-1,k}$。答案为 $dp_{n,n}-dp_{k-1,n}$
### [CF57C](https://www.luogu.com.cn/problem/CF57C)
题意：求有多少个长度为 $n$ 的数列，每个数为 $[1,n]$ 任意一个，使其为单调不上升或不下降\
思路：显然一个合法的序列倒过来还是一个合法的，又因为可以重复那么把每个数出现次数变成一个序列，是唯一对应的，就是插板法，由于可以不选，所以是 $C_{2n-1}^{n-1}\times 2 -n$，$-n$ 是因为全相同的话倒过来没有意义
### [CF145C](https://www.luogu.com.cn/problem/CF145C)
题意：一个序列 $a$，问有多少个长度为 $k$ 的子序列，使得每个仅包含 $4,7$ 的数出现次数不超过 $1$\
思路：幸运数个数肯定多，设 $dp_{i,j}$ 前 $i$ 种里面选了 $j$ 个方案数，$dp_{i,j}=dp_{i-1,j}+dp_{i-1,j-1}\times c_i$，$c_i$ 代表 $c_i$ 代表第 $i$ 种幸运数的个数。答案枚举选几个幸运数，为 $\sum_{i=0}^{\max(m,k)} dp_{m,i}\times C_h^{k-i}$，$m,h$ 为幸运数种类与非幸运数个数
### [CF306C](https://www.luogu.com.cn/problem/CF306C)
题意：将 $w$ 个黑球与 $b$ 个白球放到 $n$ 个盒子里，装白球盒子必须相邻，第一个和最后一个盒子必须装黑球，问多少种方案（小球互不相同）\
思路：枚举白盒子的方案数 $i$，答案为 $\sum b!C_{b-1}^{i-1}\times w!C_{w-1}^{n-i-1}\times (n-i-1)$，分别代表白球摆放、黑球摆放、白盒子插到黑盒子里面的方案数
### [CF336D](https://www.luogu.com.cn/problem/CF336D)
题意：一次操作将最后两个数变成一个数，如果最后两个都是 $0$，变 $1$，否则变成 $0$。问有多少种 $01$ 序列恰好有 $n$ 个 $0$ 和 $m$ 个 $1$，使得若干次操作后，最后剩下的是 $g$\
思路：显然只看 $1$ 的位置就可以，发现第一个 $1$ 后面的数没有意义，都会变成 $0$。如果 $g$ 是 $0$，那么第一个 $1$ 的位置必须是奇数，否则只能是偶数，设位置为 $i$，那么贡献为 $C_{n+m-i}^{m-1}$。如果只有一个 $1$ 的话，它在最后的话对答案可能会 $+-1$，因为在最后的话，他会变成 $1$ 而不是 $0$
### [CF356C](https://www.luogu.com.cn/problem/CF356C)
题意：$n$ 个车厢，每个车厢有 $[0,4]$ 个人，每次操作可以调换一对人，问最少操作次数使得每个车厢有 $[3,4]$ 个人\
思路：记 $s_i$ 为人数为 $i$ 的车箱数，显然要把 $s_1,s_2$ 拼一起，贡献为 $\min(s1,s2)$。如果剩下的是 $s_1$，先加上 $\lfloor \frac{s_1}3 \rfloor \times 2$，代表将三个 $1$ 拼成 $3$，如果剩下 $2$，贡献为 $2$，否则要看有没有 $3$；剩下 $s_2$ 同理，将三个 $2$ 拼成两个 $3$，如果剩下 $1$，要看有没有 $4$
### [CF414C](https://www.luogu.com.cn/problem/CF414C)
题意：一个长 $2^n$ 序列，每次操作顺次把长为 $2^q$ 的字串翻转，然后问逆序对个数\
思路：翻转只会影响块内，记 $c_{i,0/1}$ 为所有长为 $2^i$ 的子串内，且间隔至少为 $2^{i-1}$ 的逆序对/顺序对个数，可以用归并处理。每次操作把 $i\le q$ 的 $c_{i,0/1}$ 交换就行，答案为 $\sum_{i=1}^n c_{i,0}$
### [CF431D](https://www.luogu.com.cn/problem/CF431D)
题意：求任意一个 $n$ 满足 $[n+1,2n]$ 中恰好有 $m$ 个数二进制中有 $k$ 个 $1$\
思路：显然 $n$ 越大，满足条件的数越多。因为 $n$ 的区间是 $[n+1,2n]$，$n+1$ 的区间是 $[n+2,2\times(n+1)]$，显然 $2\times (n+1)$ 与 $n+1$ 包含 $1$ 的数量相等，而又多一个 $2n+1$，所以满足条件的数量单调不降低，可以二分，。\
现在问题是怎么求 $[1,i]$ 中有多少个数中有 $k$ 个 $1$，经典套路，将 $150$ 分解成 $[0,128),[128,144),[144,148),[148,150),[150,150]$，设在第 $i$ 段，前面有 $t$ 段有东西，贡献是 $C_i^{k-t}$，因为肯定有 $t$ 个 $1$，剩下随便填
### [CF451E](https://www.luogu.com.cn/problem/CF451E)
题意：有 $n$ 个花瓶，每个花瓶有 $a_i$ 个花，选 $k$ 花有多少种情况\
思路：首先有 $C_{k+n-1}^{n-1}$，但是这样分配会有一些花瓶超过了限制，要超过限制至少需要 $a_i+1$ 花，然后剩下的花都能随便放，容斥算一下，看有几瓶花超过了。设需要 $s$ 花，那么剩下的方案数就是 $C_{k-s+n-1}^{n-1}$，加或减上
### [CF552D](https://www.luogu.com.cn/problem/CF552D)
题意：$n$ 个点，求三个点组成的面积不为 $0$ 的三角形个数\
思路：正难则反，算不合法个数。枚举一个点，看有多少个点和它组成直线斜率相同，如果有 $k$ 个，那么有 $\frac{k\times (k-1)}{2}$ 种不合法，$C_n^3-sum$ 个合法
### [CF571A](https://www.luogu.com.cn/problem/CF571A)
题意：三根木棍有初始长度，现在随便给一些木棍加一些长度，总的添加有一个上限 $l$，问添加后成为三角形的方案数\
思路：正难则反，总的方案数是 $\sum_{i=0}^l C_{i+2}^2$，组合数是插板法，因为有的木棍可以不加，所以也是 $C_{i+2}^2$。考虑不合法的，就是两个最小的加起来 $\le $ 最大的。枚举最大的，把剩下的随便放，只要不超过枚举出来的最大就行
### [CF613A](https://www.luogu.com.cn/problem/CF613A)
题意：给定一个点和多边形，把这个多边形绕这个点转一圈，求转过的面积\
思路：找到多边形离这个点最远的与最近的距离，两个圆相减一下即可，最近的距离通过做垂线，可以通过海伦公式解决，特判三点共线情况即可
### [CF660D](https://www.luogu.com.cn/problem/CF660D)
题意：给定一些点，求能组成的平行四边形个数，保证三点不共线\
思路：平四对角线互相平分，记录每条线段的中点，中点相同的线段能组成平行四边形
### [CF859E](https://www.luogu.com.cn/problem/CF859E)
题意：$n$ 个人 $2n$ 个座位，每一个人都在一个座位上，目标是一个座位。问有多少种座位排列方式，使得每个人都在初始的或目标，并且没有一个座位上有两个人\
思路：先建图，每个点出度 $0$ 或 $1$，是若干个连通块，每个连通块是树、基环树、环，还有可能包含自环。发现如果是树，那么贡献就是 $sz$，因为每一个点都有可能上移；如果是基环树或环，那么贡献是 $2$，因为环上的点可以动或不动；但是如果有自环，那么贡献为 $1$，因为谁都不能动。最后用乘法原理统计
### [CF895D](https://www.luogu.com.cn/problem/CF895D)
题意：求有多少个 $s1$ 的排列 $a$，使得 $s1<a<s2$\
思路：套路，用 $f(s2)-f(s1)-1$，现在要求小于 $a$ 的字符串个数，直接枚举第一个小于的位置就行，后面的随便选用阶乘就行
### [CF1267K](https://www.luogu.com.cn/problem/CF1267K)
题意：一个数经过一下变换生成一个序列
```cpp
long long tmp=2,a[114514],siz=0;
while(k)
{
	a[++siz]=k%tmp;
	k/=tmp;
	tmp++;
}
sort(a+1,a+siz+1);
```
给定一个数字 $x$，问有多少个 $i$ 生成的序列与 $x$ 相同\
思路：只要每个数出现次数一样序列就是一样的，相当于问有多少种排列，但是一个数 $i$ 不能放到 $k\le i$ 的时候，而且最后一个数不能为 $0$。先跑一遍任意的，再把一个 $0$ 放到最后，再跑一遍，相减一下就好了
### [CF1749D](https://www.luogu.com.cn/problem/CF1749D)
题意：一个序列，一个数能被消掉的条件是 $\gcd(a_i,i)\ne 1$，消掉之后后面的数会接上。如果一个序列有多种消除方式使得所有数都能被消掉，那么这个序列是不好的。问有多少个长度 $\le n$ 且取值范围为 $[1,m]$ 的不好序列\
思路：考虑用总方案数量减去好的，显然每次消第一个是一种，一个好序列显然是对于每一个位置 $i$，所有 $j<i$ 且 $j\ne 1$，都有 $\gcd(a_i,j)\ne 1$。进一步转化就是每个 $a_i$ 都含有 $<i$ 的所有质数
### [CF1787D](https://www.luogu.com.cn/problem/CF1787D)
题意：一个数轴初始在 $1$，每次从 $i$ 跳到 $i+a_i$。现在你可以将一个 $a_i$ 变成 $x,-n\le x \le n$，问有多少种变换方式使得最后能在有限步内走出去\
思路：先跑一遍搜索，记录 $vis_i$ 代表 $i$ 这个点是由哪里来的。直接建图，然后分类讨论。如果 $1$ 本身就能走出去的话，$vis_i=1$ 的点的只能连到后面的或者自己直接跳出去，因为前面会成环；$vis_i\ne 1$ 的点可以随便连，贡献是 $2n+1$。如果 $1$ 本身不能走出去，在这个环上的点必须连到可以走出去的点或者直接跳出去
### [CF1794D](https://www.luogu.com.cn/problem/CF1794D)
题意：给定一个数质因数分解后的 $2n$ 个底数与质数（顺序不定），问初始数的可能性\
思路：设 $dp_{i,j}$ 为前 $i$ 个里面选了 $j$ 个当底数的方案数。如果 $a_i$ 为质数，$dp_{i,j}=\sum \frac{dp_{i-1,j}}{c_{a_i}!}+\sum \frac{dp_{i-1,j-1}}{(c_{a_i}-1)!}$，除以是因为有相同的。如果 $a_i$ 不是质数，$dp_{i,j}=\sum \frac{dp_{i-1,j}}{c_{a_i}!}$，代表只能当指数。初始化为 $dp_{0,0}=1$，然后第一维可以去掉，答案为 $dp_n\times n!$，因为没有考虑指数的排列方式
### [CF1942G](https://www.luogu.com.cn/problem/CF1942G)
题意：三种卡片，抽到后可以再抽 $0,1,2$ 次，初始可以抽 $5$ 次，有 $5$ 张特殊卡，求都抽到的概率\
思路：第二种卡对答案没有影响，第一种卡相当于少抽一次，第三种相当于多抽一次，而初始有 $5$ 次。设 $P(x,y)$ 为有 $x$ 张一类，$y$ 张二类，中途没有停止的方案数。相当于从 $(0,5)$ 走到 $(x,y+5)$ 且不越过 $y=x$，越过的话相当于走到 $(y+6,x-1)$，贡献就是 $C_{x+y}^y-C_{x+y}^{y+5}$。所以枚举抽了 $i+5$ 张一类， $i$ 张二类，贡献为 $f(i+4,i)\times C_{i+5}^5\times C_{a-i+c-i}^{a-i}$，最后再除以总的 $C_{a+c+5}^{a+5}$，需要特判可以全抽完的情况
### [CF1976E](https://www.luogu.com.cn/problem/CF1976E)
题意：初始集合里包含一个排列，$q$ 次操作，每次取出一个长度 $\ge 2$ 的序列，将其划分成两段，记 $l_i,r_i$ 为前半段。给定每次的 $l_i,r_i$ 求原本排列的可能性\
思路：手玩一下样例发现输入的 $l_i,r_i$ 的相对位置是被固定了，可以用链表维护插入，最后遍历一下就能知道初始序列了。现在问题就变成了插入自由数的方案数，发现相邻的两个固定数只能插入 $\le min(l,r)$ 的数，所以用 $s_i$ 代表 $\le i$ 的数的位置数，$s_{\min(l,r)}$ 加一，然后做一个后缀和就行。注意自由数要从大到小放，这样每次会多出来一个位置，而从小到大就不一定有这个性质了
### [CF2037G](https://www.luogu.com.cn/problem/CF2037G)
题意：$i,j$ 连边条件是 $i<j,\gcd(a_i,a_j)\ne 1$，问 $1$ 到 $n$ 的路径数\
思路：朴素 $DP$，$dp_i=\sum dp_j(j<i,\gcd(a_i,a_j)\ne 1)$。优化一下，由于 $a_i$ 最多有 $8$ 个质因子，只要包含其中一个的 $j$ 就可以对 $i$ 贡献。设 $b_i$ 为包含 $i$ 这个因子的所有 $dp$ 值之和，把 $i$ 拆分之和直接从 $b$ 遗传过来，然后容斥一下，最后用容斥更新 $b$ 
### [CF2065G](https://www.luogu.com.cn/problem/CF2065G)
题意：如果一个数可以分成两个质数相乘，那么这个数是半质数。问有多少个 $i,j$ 满足 $i\le j$ 且 $\operatorname{lcm(a_i,a_j)}$ 为半质数\
思路：首先可以通过筛法筛出所以半质数。如果 $a_i$ 是质数，那么 $a_j$ 是与 $a_i$ 不相等的质数；如果 $a_i$ 是半质数，且等于 $p\times q$，那么它只能与 等于 $p,q,a_i$ 的 $a_j$ 一起；其他情况不可能。开一个桶记录一下半质数与质数出现情况就行
# 动态规划
## 线性DP
### [CF46E](https://www.luogu.com.cn/problem/CF46E)
题意：一个矩阵，从每行开头选若干个数 $c_i$，要求 $c_i$ 为波浪，求所有数之和最大值\
思路：$dp_{i,j}$ 为前 $i$ 行，最后一次选 $j$ 列的最大之和，通过 $i$ 的奇偶性来转移，$dp_{i,j}=\max dp_{i-1,k}+\sum_{p=1}^j a_{i,p}$ 这样是 $n^3$ 的。思考是通过哪里转移，发现每 $j$ 每多 $1$，$k$ 就多 $1$，其他的部分与 $j-1$ 是相等的，所以用 $\max(dp_{i,j-1}+a_{i,j},dp_{i-1,j-1}+sum)$ 更新，代表之前的和最新的
### [CF213B](https://www.luogu.com.cn/problem/CF213B)
题意：构造一个 $n$ 位数，没有前导 $0$，且数字 $i$ 出现的次数 $\ge a_i$，求这样的 $n$ 位数有多少个\
思路：设 $dp_{i,j}$ 代表前 $i$ 位数，已经解决 $j$~$9$ 的情况数。

初始化为 $dp_{i,9}=[i\ge a_9]$。

- 当 $j$ 不为 $0$ 时，转移为 $dp_{i,j}=\sum_{k=0}^{i-a_j}dp_{k,j+1}\times C_i^{i-k}$，意义是找到一个能填下 $a_j$ 个 $j$ 的位置转移，然后组合数算填的方法。
- 当 $j=0$ 时， $dp_{i,j}=\sum_{k=0}^{i-a_j}dp_{k,j+1}\times C_{i-1}^{i-k}$，因为不能有前导 $0$。

答案显然为 $\sum_{i=1}^{n}dp_{i,0}$。

注意 $dp_{0,j}$ 也是要用到的，所以要从 $i=0$ 开始。
### [CF222E](https://www.luogu.com.cn/problem/CF222E)
题意：给定多个限制，求有多少个长度为 $n$ 的序列满足由 $1$~$m$ 组成，且相邻两个数不为给定限制\
思路：设 $dp_{i,j}$ 为前 $i$ 个数最后一个为 $j$ 的方案数，$mp_{i,j}$ 为 $i,j$ 挨在一起是否合法，则 $dp_{i,j}=\sum_{k=1}^mdp_{i-1,k}[mp_{k,j}=1]$。每次转移是相同的，可以矩阵快速幂加速。

假设限制为 $(1,2),(2,3),(3,1)$，转移为
$$
\begin{bmatrix}
 dp_{i-1,1} & dp_{i-1,2} &dp_{i-1,3}
\end{bmatrix}\times
\begin{bmatrix}
  1&  0& 1\\
  1&  1& 0\\
  0&  1&1
\end{bmatrix}=

\begin{bmatrix}
 dp_{i,1} & dp_{i,2} &dp_{i,3}
\end{bmatrix}$$

将初始矩阵乘以转移矩阵的 $n$ 次方即可
### [CF295C](https://www.luogu.com.cn/problem/CF295C)
题意：一个船载重 $k$，有 $n$ 个人要过去，每个人体重为 $50$ 或者 $100$，问最少往返次数以及此情况下的方案数\
思路：设 $dp_{i,j,k}$ 为第 $i$ 次乘船，还剩下 $j$ 个 $50$ 和 $k$ 个 $100$。分类讨论这次是过去还是回来，然后枚举这次船上的人数 $s1,s2$，乘上组合数。注意 $4n$ 内一定能回来（一个大的自己过去，然后让一个小的回来），如果超过 $4n$ 说明无解
### [CF479E](https://www.luogu.com.cn/problem/CF479E)
题意：$n$ 层楼，初始在 $a$，每次从 $x$ 走到 $y$ 要满足 $|x-y|<|x-b|$，问走 $k$ 次的方案数（过程不一样就算不一样）\
思路：设 $dp_{i,j}$，为走了 $i$ 次，目前在 $j$ 层的方案数，$dp_{i,j}=\sum_{l}^r dp_{k,j}[k\ne j]$，第一维没用。发现当 $a<b$ 时，不能走 $\ge b$ 的层，当 $a>b$ 时，不能走 $\le b$ 的层。为了方便转移，把 $b$ 设成 $0$，这样 $l=\frac{j}2,r=n$
### [CF489F](https://www.luogu.com.cn/problem/CF489F)
题意：一个 $m\times n$ 的 $01$ 矩阵，问有多少种方法能补成一个 $n\times n$ 矩阵，使得每行每列之和都为 $2$\
思路：设 $dp_{i,j,k}$ 为前 $i$ 行，有 $j$ 列和为 $0$，$k$ 列和为 $1$，$n-j-k$ 列为 $2$ 的方案数，答案为 $dp_{n,0,0}$，初始状态为输入的矩阵。每行相当于给两列加一，转移看是把哪两列加一就行，注意要判掉一些不合法的 $j,k$，这样可以优化
### [CF551D](https://www.luogu.com.cn/problem/CF551D)
题意：有多少个长度为 $n$ 的序列，使得 $(a_1\text{ and } a_2)\text{ or }(a_2\text{ and } a_3)\text{ or } \dots(a_{n-1}\text{ and } a_n)=k$，且 $a_i <2^{l-1}$\
思路：把 $k$ 二进制拆分，每一位互不影响。设 $dp_{i,0/1}$ 为前 $i$ 个数，按照上面操作下来是 $0$,并且第 $i$ 个数是 $0/1$，$dp_{i,0}=dp_{i-1,0}+dp_{i-1,1},dp_{i,1}=dp_{i-1,0}$，是斐波那契数列，用矩阵快速幂加速。如果 $k$ 的第 $i$ 位为 $0$，贡献为 $dp_{n,0}+dp_{n,1}$，否则贡献为 $2^n-dp_{n,0}-dp_{n,1}$，乘一起就行
### [CF691E](https://www.luogu.com.cn/problem/CF691E)
题意：有 $n$ 个数，求能组成多少个长度为 $k$ 的序列，使得相邻两项异或值 $1$ 的个数是 $3$ 的倍数\
思路：设 $dp_{i,j}$ 为前 $i$ 个数最后一个为 $a_j$ 的方案数，$mp_{i,j}$ 为 $i,j$ 挨在一起是否合法，则 $dp_{i,j}=\sum_{k=1}^mdp_{i-1,k}[mp_{k,j}=1]$。每次转移是相同的，可以矩阵快速幂加速。

假设不合法的放法为 $(a_1,a_2),(a_2,a_3),(a_3,a_1)$，转移为
$$
\begin{bmatrix}
 dp_{i-1,1} & dp_{i-1,2} &dp_{i-1,3}
\end{bmatrix}\times
\begin{bmatrix}
  1&  0& 1\\
  1&  1& 0\\
  0&  1&1
\end{bmatrix}=

\begin{bmatrix}
 dp_{i,1} & dp_{i,2} &dp_{i,3}
\end{bmatrix}$$

将初始矩阵乘以转移矩阵的 $n$ 次方即可
### [CF404D](https://www.luogu.com.cn/problem/CF404D)
题意：给定一个一维扫雷地图，求将图中不确定的地方填上合法东西的方案数\
思路：一个 $5$ 维DP，记录前 $i$ 个数两边没有雷、左右都是雷、左边雷、右边雷、这一位是雷的方案数，转移根据这一位是什么转移。
### [CF505C](https://www.luogu.com.cn/problem/CF505C)
题意：数轴上有 $n$ 个宝藏，初始有一个跳跃距离 $d$，当上一次跳了 $x$ 步后，这一步可以跳 $x-1,x,x+1$，不可以跳负数步\
思路：设 $dp_{i,j}$ 为跳到第 $i$ 步，且上一次跳跃距离与 $d$ 的差为 $j$，这样 $dp_{i,j}=\max(dp_{i-(d+j),j-1},dp_{i-(d+j),j},dp_{i-(d+j),j+1})$，因为 $j$ 可能为负数，所以要加一个偏移量
### [CF540D](https://www.luogu.com.cn/problem/CF540D)
题意：石头 $a$ 个，剪刀 $b$ 个，布 $c$ 个，每次随机选两个不相同的，输的人出局，问最后只剩下石头、剪刀、布的概率\
思路：设 $dp_{i,j,k}$ 为剩下 $i$ 个石头，$j$ 个剪刀，$k$ 个布的概率。转移就看选到哪两个就行。答案就是 $\sum dp_{i,0,0},\sum dp_{0,i,0},\sum dp_{0,0,i}$
### [CF568B](https://www.luogu.com.cn/problem/CF568B)
题意：
构造一个集合，集合内的元素是一对数 $(x,y)$，$a,b$ 的范围是 $[1,n]$，要求满足一下性质：

- 如果有 $(x,y)$，那么有 $(y,x)$
- 如果有 $(x,y)$ 和 $(y,z)$，那么有 $(x,z)$
- 集合不能为 ${(1,1),(2,2),(3,3)\dots (n,n)}$
- $x,y,z$ 可以相等

求满足条件的集合数

思路：设 $dp_{i,j}$ 为前 $i$ 个数分成 $j$ 个集合的方案数，设 $s_i=\sum_{j=1}^{j=n}{dp_{ij}}$。合法方案可以由 $n$ 个数里选 $i$ 个数得来，答案为 $1+\sum_{i=1}^{n-1}{C_n^i}s_i$，$1$ 为空集的方案。
### [CF577B](https://www.luogu.com.cn/problem/CF577B)
题意：给定一个长为 $n$ 的数组 $a$，求将 $a$ 循环 $k$ 次后组成的数组的最长不下降的子序列长度\
思路：
- $k \le n$ 时，直接暴力跑就行。
- $n<k$ 时，显然有一段应该重复去选，考虑选 $1,2,2\dots 2,3$ 与 $1,2,3,3,3\dots$ 是等价的，所以直接选 $a$ 里面出现次数最多的。

综上，先跑长度为 $n\times \min(n,k)$ 的最长不下降子序列，然后如果 $n<k$ 就去选出现次数最多的 $\times (k-n)$。
### [CF597C](https://www.luogu.com.cn/problem/CF597C)
题意：给定长度为 $n$ 的排列 $a$，求 $a$ 中长度为 $k+1$ 的上升子序列个数\
思路：设 $dp_{i,j}$ 为以 $i$ 为结尾长度为 $j$ 的上升子序列个数，$dp_{i,j}=\sum_{a_l<a_i}dp_{l,j-1}$，可以去掉 $j$ 这一维，然后求和部分可以通过树状数组加速。发现 $k$ 很小，所以直接跑 $k$ 次转移就行。
### [CF682D](https://www.luogu.com.cn/problem/CF682D)
题意：求从 $s,t$ 里选出 $k$ 个不交的子串，$s,t$ 的第 $i$ 个子串必须相等，求长度之和的最大值\
思路：设 $dp_{i,j,k,0/1}$ 代表 $s$ 里面选到 $i$，$t$ 里面选到 $j$，已经选出来 $k$ 个子串，$i,j$ 是/否匹配。$dp_{i,j,k,0}=\max(dp_{i-1,j,k,0/1},dp_{i,j-1,k,0/1},dp_{i-1,j-1,k,0/1})$，如果 $a_i=b_j,dp_{i,j,k,1}=\max(dp_{i-1,j-1,k-1,0},dp_{i-1,j-1,k,1})$
### [CF1101D](https://www.luogu.com.cn/problem/CF1101D)
题意：最长一条链，使得所有点权 $\gcd>1$\
思路：分解质因数，看两个数有没有共同质因数，有就接上
### [CF1606E](https://www.luogu.com.cn/problem/CF1606E)
题意：一开始有 $n$ 个人，每轮所有存活的人会想其他人造成 $1$ 点伤害，同时结算，一个人血量 $<1$ 就死了，让你给每个人分配一个 $1$ 到 $k$ 的血量使得只有 $1$ 个人存活，问分配方案数量\
思路：设 $dp_{i,j}$ 为 $i$ 个人最大血量为 $j$ 的方案数，初始化为 $dp_{i,j}=j^i-(j-1)^i(i>j)$，转移枚举死了 $k$ 个人，$dp_{i,j}=\sum_{k=0}^{i-1}dp_{i-k,j-i+1}\times C_i^k\times (i-1)^k$
### [CF1928E](https://www.luogu.com.cn/problem/CF1928E)
题意：构造一个和为 $s$ 的序列，使得 $a_1=x$，且 $a_{i+1}=a_i+y$ 或 $a_{i+1}=a_i\bmod y$\
思路：因为放的 $y$ 是固定的，每个 $a_i$ 相当于 $x\bmod y+k\times y$，所以相当于若干个公差为 $y$ 的数列，设 $dp_i$ 为凑出来 $i$ 需要的最小长度，对于每一个 $i$，看里面最后一段数列长度为多少，记录转移的长度。最后统一赋值
### [CF1993D](https://www.luogu.com.cn/problem/CF1993D)
题意：每次删掉一个长为 $k$ 的子串，直到删不动\
思路：二分答案，设 $dp_i$ 为前 $i$ 个数中，大于 $mid$ 的数减去小于 $mid$ 的数的最大值，如果 $dp_n>0$ 说明 $mid$ 可以更大，否则不行。
$$
b_i=\left\{\begin{matrix}
 1 & a_i\ge mid\\
 -1 & a_i<mid
\end{matrix}\right.$$
$$dp_i=\left\{\begin{matrix}
 \max(dp_{i-k,b_i})& k|i-1\\
 \max(dp_{i-k},dp_{i-1}+b_i)& i\ge k+1\\
dp_{i-1}+b_i& else
\end{matrix}\right.$$
如果 $i-1$ 是 $k$ 的倍数，说明不能选 $i-1$，因为不能选超过 $k$ 个；否则就讨论能不能从 $i-k$ 来就行
### [CF2001E1](https://www.luogu.com.cn/problem/CF2001E1)
题意：一个满二叉树且为大跟堆，每次操作将一个点到根节点的节点权值加一，一次pop操作为把最大的去掉，问 $k$ 次加法后，再进行若干次pop操作能获得的不同二叉树形态个数\
思路：设 $dp[i][j]$ 为第 $i$ 层，操作 $j$ 次的方案数，然后设 $g[i][j]$ 为不保证左右儿子权值不相等，$dp$ 保证，则有：
$$g[i][j]=\sum_{x=0}^j\sum_{y=0}^{j-x}g[i+1][x]*g[i+1][y]$$
$$f[i][j]=2\times \sum_{x=0}^j\sum_{y=0}^{\min(j-x,x-1)}f[i+1][x]*g[i+1][y]$$
## 背包DP
### [CF678C](https://www.luogu.com.cn/problem/CF687C)
题意：问有多少个 $x$，使得和为 $k$ 的子序列里有和为 $x$ 的子集\
思路：设 $dp_{i,j,p}$ 为前 $i$ 个数，和为 $j$ 的子集里是否能凑出来 $p$，根据选不选 $a_i$ 转移
## 区间DP
### [CF607B](https://www.luogu.com.cn/problem/CF607B)
题意：长度为 $n$ 的序列 $a$，每次可以删除一个回文子串，求删除所有数需要的最小次数。\
思路：简单区间dp，设 $dp_{i,j}$ 代表删除 $i$~$j$ 的最小代价，转移很简单
## 树形DP
### [CF558C](https://www.luogu.com.cn/problem/CF558C)
题意：一个长度为 $n$ 的序列 $a$，每次可以把$a_i$ 变成 $a_i \times 2$ 或 $\lfloor \frac{a_i}{2} \rfloor$，求将所有 $a_i$ 都相等的最小操作数\
思路：把操作放到二进制下看，就是往后面加一个 $0$ 或删除最后一位。\
建一个二叉树，节点 $p$ 连向 $p\times2,p\times 2 +1$，将 $a_i$ 放到树上，两种操作变成往上走或往左走。转化成求一个根节点，使所有 $a_i$ 往上移动的步数之和最小。\
建树时先记录每棵子树内有多少个 $a_i$，然后找到一个根节点后，开始换根，每次都往左走的同时更新答案。
### [CF1929D](https://www.luogu.com.cn/problem/CF1929D)
题意：一个树，有多少个点集，使得所有路径经过点集上的点的个数 $\le 2$\
思路：$dp_{i,1/2}$ 为 $i$ 的子树内，经过 $i$ 的路径中恰好有 $1/2$ 个标记点的方案数量。$dp_{i,1}$ 只能是子节点都不选自己选或者子节点有至少一个选 $1$，$dp_{i,2}$ 可以是自己选子节点只有一个选或者只有一个子节点选 $2$。
### [CF1363E](https://www.luogu.com.cn/problem/CF1363E)
题意：可以花 $a_i \times k$ 的代价把以 $i$ 为根节点的子树内的 $k$ 个节点重排 $b_i$，问最小代价使 $b_i=c_i$\
思路：开一个桶记录不行的情况，然后回溯的时候选
## 数位DP
### [LOJ 10168](https://loj.ac/p/10168)
题意：问 $[L,R]$ 满足以下条件数的平方和
- 没有 $7$
- 数位和不是 $7$ 的倍数
- 这个数不是 $7$ 的倍数

思路：数位DP，从高往低填，维护个数、和、平方和。注意只有随便填的时候才可以记忆化
### [P2657](https://www.luogu.com.cn/problem/P2657)
题意：求 $[L,R]$ 内有多少个数满足相邻两个数位的差 $\ge 2$\
思路：记忆化搜索，但要记录前面有没有前导 $0$
### [P4127](https://www.luogu.com.cn/problem/P4127)
题意：求 $[L,R]$ 内有多少个满足数位和能整除这个数\
思路：记忆化搜索，但是由于是整除还需要记录这个数模数位和，但是数位和会变，所以要枚举数位和
### [P11557](https://www.luogu.com.cn/problem/P11557)
题意：求 $[L,R]$ 内有多少数满足数位单调不递减\
思路：记忆化搜索，记录上一次选了啥，注意 $L,R \le 10^{100}$ 所以直接倒序输入到数组里，然后用 $f(R)-f(L)$ 在加上 $L$ 是否合法
## 状压DP
### [P3622](https://www.luogu.com.cn/problem/P3622)
题意：每个人都希望一段长为 $5$ 区间内有几个数中有不选或有几个数中被选，让你安排每个数选或不选，使满意的人最大\
思路：$dp_{ij}$ 代表前 $i$ 个数 第 $i$ ~ $i+4$ 个数选的情况为 $j$ 能获得的最大满意度，从 $i-1$ 的 $j$ 的后四位后面再加或不加 $1$ 来转移，最后加上这一段的价值 
### [CF510D](https://www.luogu.com.cn/problem/CF510D)
题意：$n$ 个数，每个数有一个价格，选若干个数使得 $\gcd=1$ 求最小花费\
思路：把每个数分解质因数，枚举一个数必选数 $i$，当前这轮目标就是把 $i$ 的质因子都搞掉，设 $dp_k$ 为当前质因子状态为 $k$，初始状态为 $dp_{2^{len_i}-1}=cost_i$ 枚举选的数 $j$，记录共同出现的质因子状态 $s$，那么 $dp_{k\wedge s}=\min(dp_k+cost_j)$，答案为 $\min(dp_0)$
## 期望DP
### [P3232](https://www.luogu.com.cn/problem/P3232)
题意：在图上随机游走，在 $n$ 点结束，给每个边编号，使总分期望最小\
思路：先算每个点经过次数期望 $f_u=\sum_{u,v} \frac{f_v}{d_v}$，需要高斯消元解决，然后再算每个边期望 $g_i=\frac{f_u}{g_u}+\frac{f_v}{g_v}$，将 $g$ 排序后赋值即可
### [P4273](https://www.luogu.com.cn/problem/P2473)
题意：$k$ 轮，每次会随机出一个物品，当这个物品的前置物品你都拥有后，你可以获得这个物品的价值（可能为负数），求最大期望值\
思路：设 $dp_{ij}$ 表示 $1$ 到 $i-1$ 轮获得的宝物为状态为 $j$ 剩下的轮次能获得的最大期望，按选不选转移即可
### [CF500D](https://www.luogu.com.cn/problem/CF500D)
题意：一棵树，进行 $q$ 次操作，每次修改一条边边权。然后等概率选择 $c1,c2,c3$，求 $d(c1,c2)+d(c2,c3)+d(c1,c3)$ 的期望\
思路：考虑每一条边贡献，假设 $u$ 是 $v$ 的父亲，那么那么贡献即为 $(C_{sz_v}^2\times (n-sz_v)+C_{n-sz_v}^2\times sz_v)\times w\times 2$，乘以二是因为每种情况这条边都会被经过两侧。每次修改就减去原本贡献，再加上现在贡献即可
### [CF1753C](https://www.luogu.com.cn/problem/CF1753C)
题意：一个长度为 $n$ 的 $01$ 序列，每次随机抽取 $i,j$，当 $a_i > a_j$ 时交换 $a_i,a_j$，问使 $a$ 从小到大排序需要操作的期望数\
思路：设 $a$ 里有 $m$ 个 $0$，前 $m$ 个数里有 $k$ 个 $0$，题目要求前 $m$ 个数全为 $0$。设 $dp_i$ 为前 $m$ 个数有 $i$ 个 $0$ 的期望，那么 $dp_k=0$，每次可以交换的方案数为 $C_n^2$，每次合法的交换方法为前 $m$ 个数里的 $1$ 和后面数的 $0$，为 $(m-i+1)^2$。所以 $dp_i=dp_{i-1}+\frac{C_n^2}{(m-i+1)^2}$，答案为 $dp_m$
### [CF1925D](https://www.luogu.com.cn/problem/CF1925D)
题意：有 $n$ 个人 $m$ 对朋友，每对朋友有一个友谊，老师要选择 $k$ 次。每次选择两个不相同的人，如果是朋友，那么之后的选择里他们友谊值都会 $+1$。求最后友谊值之和期望值\
思路：设 $dp_i$ 为第 $i$ 次选择后的期望，$p=\frac{2}{n\times (n-1)}$ 为抽到一对人的概率。$x_j$ 为第 $j$ 组的期望，$dp_i=dp_{i-1}+\sum x_j\times p$。对于每组朋友，有 $p$ 的概率 $+1$，$1-p$ 的概率不变，所以期望 $+p$，$x_j$ 每次 $+p$。所以 $dp_i=\sum{w_j+m\times(i-1)\times p}$。最后只需要维护一个当前和即可，每次加 $p\times m$，代表包括之前加的还有现在新来的
## 斜率优化
### [P3648](https://www.luogu.com.cn/problem/P3648)
题意：每次分割产生的分数为分割后产生的两个块分数和的乘积，求分割 $k$ 次后的最大分数\
思路：$dp[i][j]$ 代表前 $i$ 个数分割 $j$ 次产生的最大分数，暴力转移为 $dp[i][j]=max(dp[i][j],dp[i-1][k]+s[k]*(s[i]-s[k])$，然后滚动数组滚掉一维，然后斜率优化。
$$dp[i]=dp[j]+s[j]*(s[i]-s[j]$$
$$dp[j]+s[j]*s[i]-s[j]^2>dp[k]+s[k]*s[i]-s[k]^2$$
$$dp[j]-s[j]^2-(dp[k]-s[k]^2)>(s[k]-s[j])*s[i]$$
$$\frac{dp[j]-s[j]^2-(dp[k]-s[k]^2)}{-s[j]-(-s[k)}>s[i]$$

正在渲染内容...