CH 4201
题意：给出$n$点个点$(i,y_i)$，
若存在三点$(x_1,y_1), (x_2,y_2),(x_3,y_3)$，满足$x_1 > x_2 > x_3, y_1 > y_2, y_3 > y_2$则这三点称为v
若存在三点$(x_1,y_1), (x_2,y_2),(x_3,y_3)$，满足$x_1 > x_2 > x_3, y_1 < y_2, y_3 < y_2$则这三点称为^

请计算v, ^的个数

方法1：
根据$y$排序，对于^，每次加入一个点前询问比这个点$y$值小的$[1,x)$和$(x, INF)$的点的个数，答案加上他们的乘积，对于v同理

方法2：
根据$x$排序，对于v，对于每个数算出左右比$y$他大的点的个数，答案加上他们的乘积，对于^同理

poj 1733
有字符串，由$0$和$1$组成，给出几个区间，并且告诉你区间里面$1$的个数的奇偶性，假设前面的话都是对的，问你到哪一句和前面的话矛盾。

这种题肯定想图论问题。
对于区间，转化为前缀和相减。那么前缀和奇偶性相不相同就能确定了。
若区间为奇数则奇偶性不同，否则奇偶性相同。
然后拆点并查集判关系即可。

BZOJ 4195
题意：给出$n$组关系，$x_i=x_j$或$x_i≠x_j$，请判断是否能有一种方法满足情况。

想到图论就不难了……
显然将等于看作无向边，然后一个联通块的都是相等的。
然后再枚举每个不等的二元组，判是否在一个联通块即可。
用并查集维护。

注意要离散化。

BZOJ 1951
题意：给定$N,G$, 求
$$
G^{\sum_{K|N}C^{\frac NK}_{n}} \mod 999911659
$$

根据欧拉定理推论
$$
a^b \equiv a^{b \mod \varphi(n)} \pmod {n}
$$
以及$999911659$为质数，可以得到
$$
G^{\sum_{K|N}C^{\frac NK}_{n} \mod 999911658} \mod 999911659
$$
那么主要就是求$\sum_{K|N}C^{\frac NK}_{n} \mod 999911658$。
这个可以用 Lucas 来解决，但是模数不一定是质数，我们就要想分解因数再合并。

因为$999911658=2 \times 3 \times 4679 \times 35617$，所以我们可以解出答案模$2,3 ,4679, 35617$意义下的$4$个解，记为$a_i$，那么算完后我们通过以下方程组解得$x$即可求出最终结果：
$$
\begin{cases}
x \equiv a_1 \pmod {2} \\
x \equiv a_2 \pmod {3} \\
x \equiv a_3 \pmod {4679} \\
x \equiv a_4 \pmod {35617}
\end{cases}
$$
显然是中国剩余定理，最终解是在模$2 \times 3 \times 4679 \times 35617=999911658$意义下的，所以符合题意。
然后再快速幂算出最后答案即可。注意特判$999911659|G$的情况。

bzoj 2973
题意：见上。
我们考虑一维怎么做，其实二维就可以在一维基础上标号即可。
然后对于原题就是一个矩阵转化的过程。根据$T$很大也可以看出。
操作序列不一样长可以求个$lcm$然后都等长，因为$lcm(1,2,…,6)=60$，所以不会很大
根据转移矩阵构造方法：若状态矩阵中的第 $x$ 个数对下个单位时间状态矩阵的第 $y$ 个数产生影响，则吧转移矩阵的第 $x$ 行第$ y$ 列赋值为适当的系数
对于方向的移动，我们让$(x,y)->(x+dx,y+dy)=1$
对于数字的增加，我们让$(0,y)->(x,y)=x, (x,y)->(x,y)=1$
此时我们就要保证$(0, 0)->(0, 0)=1$，否则转移就没了
对于D，不用额外操作。
然后矩阵快速幂求$lcm$的整块即可。不完整的块暴力。

poj 3696
题意：给定$L$, 求最少几个$8$组成的数是$L$的倍数。
对于这个$8$数来说，他的表示方法可以是$\sum^{n-1}_{i=0} 8 \cdot 10^i$。这样明显很不方便，我们想到学数列时的表示方法，$\frac{8(10^x-1)}{9}$。
本题就是要求$L|\frac{8(10^x-1)}{9}$的最小$x$解。
我们将分数先消掉，得$9L|8(10^x-1)$，然后这个整除式等同于同余式$8(10^x-1) \equiv 0 \pmod {9L}$
再进行化简，得$10^x \equiv 1 \pmod {\frac{9L}{gcd(8,9L)}}$ (同余基本性质)

引理: $a^x \equiv 1 \pmod{n}$的最小正整数解为$\varphi(n)$的约数。

具体可以用反证法+设带余除法形式证明。

然后应用在本题就是求出对应的$\varphi$值然后用试除法找每个因子用最开始的同余式判断即可。注意快速幂的取模，由于是模意义下的。

本题数据大要快速乘解决溢出的问题

BZOJ 1975
题意：求有向图中最多的几条路径和小于一个值。
很容易想到先求最短路，再求次短路，再求第三短路，然后值一直减下去直到不够为止。
所以就是明显的$k$短路模板了。
用 Astar 算法可以解决。我们想一个问题，在求最短路中，若不考虑松弛关系，则第$k$次出队的最短路就是$k$短路。
所以我们可以 优先队列 BFS，在不超过限定的$k$短路时一直搜。
但是这复杂度最坏能到$O(k(n + m)log(n+m))$，直接爆炸
我们尝试为BFS增加一个估价函数，即搜到某个点时的实际距离$dis(u)$，估计一下到终点最小走多少距离$g(u)$，$f(u)=dis(u)+g(u)$即为估价函数。我们将这个设为堆的关键字拓展就能减少很多枚举。这就是 Astar 算法
Astar 算法就是：有估价，其中估价一定要比实际的更优，其实是一种最优化剪枝 (对未来预测，按最低标准来讲)
注意在 Astar 中不用存当前的$dis(u)$，因为这个是被不断更新的，只需要判断不超过限定的$k$短路即可

剪枝：
1、设定最大的$k$，所有点只要出队不小于$k$次都剪枝，因为这样到终点一定会超过$k$

poj 1830
题意：见上。
设$x_i$为$i$开关是否(0/1)操作，$a_{i,j}$为$j$开关操作后是否(1/0)会影响$i$开关

则可以列出线性异或方程组

$$
\begin{cases}
a_{1,1}x_1 xor a_{1,2}x_2 xor … xor a_{1,n}x_n = st_1 xor ed_1 \\
a_{2,1}x_1 xor a_{2,2}x_2 xor … xor a_{2,n}x_n = st_2 xor ed_2 \\
\vdots \\
a_{n,1}x_1 xor a_{n,2}x_2 xor … xor a_{n,n}x_n = st_n xor ed_n
\end{cases}
$$

高斯消元即可。

Codeforces 981D
题意：给定$n$个数数列，求将数列分成$k$部分的和按位与的最大值。
最开始认为DP但是不符合子结构最优性质……
但是我们可以转化为存在性 DP，我们发现题目的所求答案不会大于$2^{50} \times 50$
根据位运算性质，我们贪心地，二进制下取高位一定是比取下所有低位的优的，所有我们要不遗余力地尽可能取高位，所以从高位开始枚举检验能不能取。可以用存在性DP来判。具体实现可以看代码实现

CH 2101
题意：给定一张$n$个点$m$条边的有向无环图，分别统计从每个点出发能够到达的点的数量。

DAG图想到 DP / 拓扑，这里显然 DP，设 $dp(u) $为$u$的可达点二进制集合 (bitset)，则
$$
dp(u)= x \cup (\bigcup_{(u,v) \in E} dp(v))
$$

答案为
$$
\sum_{i=1}^n |dp(i)|
$$

记忆化搜索即可，集合用 bitset 维护。