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

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

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

Codeforces 1181D
题意：

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

知识点：
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)!
$$
那么就能容斥了。

BZOJ 2111
题意：称一个$1,2,…,N​$的排列$P_1,P_2…,P_n​$是$\text{Magic}​$的，当且仅当$2 \leq i \leq N​$时，$P_i > P_{\frac i2}​$. 计算$1，2，…N​$的排列中有多少是$\text{Magic}​$的，答案可能很大，只能输出模$P​$以后的值

容易转化为即求小根堆的方案数。
那么我们可以用树形DP方法来做，设$dp(i)$为以$i$为根($P$的下标$i$)的方案数。
那么这个树的左右子树大小是定的，那么就有
$$
dp(i)=C^{s-1}_{n-i} dp(ls) \cdot dp(rs)
$$
其中$ls, rs$为左右子树大小，$s$为$i$子树大小
即$i$子树候选集合大小为$n-i$，从候选集合选出$s-1$个来当$i$的子树，然后分别乘上左儿子右儿子的方案即可。

Loj 6185
题意：求$n$个点的每个点度数不超过$4$且根的度数不超过$3$的有根树的数目。

显然有一个暴力DP方法，复杂度取决于根度数

考虑$dp$一颗一颗子树加进去方案，从小到大加可以不重不漏。
这里我们设$dp(s,i,j)$为当前添加的子树大小不超过$s$，有$i$个节点，根节点$j$度的方案数。

考虑枚举添加的子树个数$k$，那么这$k$个$s$大小的子树占用了$ks$个节点和$k$度，那么可以从$dp(s-1,i-ks,j-k)$转移过来。然后考虑将$k$棵子树乘上他们的方案。

设$a_i=\sum\limits_{g=0}^{m-1} dp(s-1, i, g)$，那么$a_s$就是$s$大小子树的方案‘
考虑将$k$棵子树分成$a_s$份(可以留空)，方案数为$C^{a_s-1}_{a_s+k-1}$

那么得到转移方程
$$
dp(s,i,j)=\sum_{k=0}^{k \leq j, ks - 1 \leq i} dp(s-1,i-ks,j-k) \cdot C^{k}_{a_s+k-1}
$$

由于$a_s-1$较大，而$k \leq m=3$, 则转化一下方便求组合数。
注意到第一维可以不需要存储，类似背包滚动数组的方法，所以$i$要倒序

时间复杂度$O \left( n^2 m \log m \right)$。

知识点：
1、计数DP要按顺序加才能不重不漏
2、有根树统计可以用加子树的顺序

Codeforces 1163E
题意：给定集合$S$, 求出一个$x$最大的$[0, 2^x-1]$排列，使得任意两个相邻元素异或值在$S$中。

设$S$的线性基为$T$
1、$[0, 2^x-1]$可以被构造出来当且仅当$[0, 2^x-1]$中的数可以被小于$2^x-1$的$T$中的元素表示出来

证明：排列中一定有$0$, $0$周围两个数$i,j$肯定$i,j \in S$，那么之后的数都可以类推然后发现就是能被$S$表示既可以，否则不行。那么只需要$T$能表示即可。

运用这个结论，边求出线性基，边计算最大满足条件的$x$

2、构造的排列相邻的两个元素在$T$中映射的bitset相差$1$位

证明：结果比较显然，不相差$1$位就不能从其他位异或一个$S$得到这个数。

那么直接DFS从0开始构造序列即可。

知识点：
1、异或题的0

Codeforces 1156F
题意：包里面有$n$个数，每次取一个数，当前取出的数为$x$，前一个取出的数为$y$,则：
若x > y，游戏继续
若x = y，游戏结束并且玩家赢
若x < y，游戏结束并且玩家输
问玩家赢的概率

容易发现必须从小取到大。
设$dp(i,j)$为删了$i$个卡牌，最大删到$j$值卡牌获胜的概率。
那么考虑取出相同值或者大于$j$值卡牌的情况，两者概率相加。具体转移方程可以看代码。
代码实现中加入一个$0$必选，不影响答案，可以方便求出答案，答案为$dp[0][0]$

BZOJ 5299
题意：见上。

可以用连接个数来划分阶段。
那么我们设$dp(S,i)$为已经连过的点的集合，最后一次连在$i$点的方案数。
然后转移即可。复杂度$O(2^n n^2)$，复杂度跑不满可以过
然后我们还要满足两个点之间的连线不能「跨过」另一个点，那么我们预处理出来两个点之间点的集合，转移时判断即可。

这个集合可以$O(n^3)$来做，就是枚举两个点$i,j$求他们的之间点集合$S_{i,j}$
那么我们再枚举一个$k$点，判下斜率相等即可确定

还可以$O(nx)$做。先求出$\Delta x = b_x - a_x, \Delta y = b_y - a_y$，我们发现整点数只会在$(a_x + \frac{\Delta x}{\gcd (\Delta x, \Delta y)}, a_y + \frac{\Delta y}{\gcd (\Delta x, \Delta y)})$
，直接找坐标是否存在给定点即可，这里用了map，其实可以用桶。可以发现这个步数不超过$\max(x,y)$

最后统计答案统计$S$二进制下$1$个数大于等于$4$的

知识点：
1、状压的空间预留不要开太大，特别是尾数

BZOJ 4571
题意：给定$a_i​$，询问$m​$次$b,x,l, r​$, 求$\max(b \text{xor} (a_i+x))​$, $i \in [l, r]​$

这里有加法就不能用01Trie的方法了。然而我们还是可以按位贪心。
考虑贪心到第$i$位，当前已经贪了的$\text{ans}=a_i+x$，那么之后如果第$i$位填上了$1$，则答案范围为$[\text{ans} + 2^{i}, \text{ans} + 2^{i+1}-1]$
$0$同理为答案范围为$[\text{ans}, \text{ans} + 2^{i}-1]$
然后我们只需要看有没有$a_i$在这个范围即可判断能不能填了。
因为区间，所以用主席树来做。

注意主席树值域要开$2 \times 10^5$

知识点
1、异或的按位贪心。

BZOJ 4571
题意：求有多少种长度为 $n$ 的序列 $A$，满足以下条件：
$[1, n]$ 这 $n$ 个数在序列中各出现了一次
若第 $i$ 个数 $A_i$ 的值为 $i$，则称 $i$ 是稳定的。序列恰好有 $m$ 个数是稳定的
满足条件的序列可能很多，序列数对 $10^9+7$ 取模。

我们可以$C^m_n$选出$m$个人来稳定，然后其他就是错位排列。
错位排列可以递推出来，设$n$个数的错位排列是$D(n)$，则有
$$
D(n)=(n-1)(D(n-1)+D(n-2))
$$
证明：考虑$n$这个数放到了$k$位置，有$n-1$种情况。
然后考虑$k$这个数放在哪
1、$k$这个数放在$n$位置，那么显然$n,k$全部被排完，变成了$D(n-2)$的局面
2、$k$这个数不放在$n$位置，那么现在先不放$k$，然后现在我们已经少了一个$n$数和$k$位置，那么其实$k$数等价于现在的$n$数，变成了$D(n-1)$的局面

这里还有一个通项式子
$$
D(n) = n! \left( 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} \cdots + (-1)^n \frac{1}{n!} \right)
$$
证明即使用容斥原理。

ps：不要忘了预处理阶乘逆元的方法求组合数。