CF1930E 2..3...4.... Wonderful! Wonderful!
我们相当于计算 \(01\) 串的个数，\(0\) 表示删除了，\(1\) 表示还保留着。
考虑 \(01\) 串合法的条件：首先 \(0\) 的个数为 \(2k\) 的倍数；其次存在 \(1\) 使得其左侧和右侧都至少有 \(k\) 个 \(0\)。
考虑从最后一次操作回退。我们选择一个 \(1\)，然后其左边和右边各选择 \(k\) 个 \(0\)，将其变为 \(1\)。
注意到：其左边和右边各选择 \(k\) 个 \(0\)，将其变为 \(1\) 之后，一定也能形成一个合法的 \(01\) 串。
关于如何计算答案，考虑容斥，相当于若干个 \(0\) 里插入 \(1\)，\(1\) 不能插在第 \(k\) 个 \(0\) 与倒数第 \(k\) 个 \(0\) 间。
最后枚举 \(k\)，复杂度是调和级数。
我经常犯得错误是计数的对象弄错，一开始设 \(f_{n,k}\)，求的是操作的方案数。
P9745 「KDOI-06-S」树上异或
一个朴素的树形 dp，设 \(f_{u,val}\) 表示 \(u\) 所在的联通块值是 \(val\) 且未闭合，所有方案积的和。
同时设 \(g_u\) 表示 \(u\) 子树已经闭合的答案。转移是：\(f_{u,val}=f_{u,val}\times g_v+\sum_k f_{u,val\otimes k}\times f_{v,k}\)。
最后 \(g_u=\sum_{val}val\times f_{u,val}\)。
观察发现第一个转移中每位之间互不干扰，而第二个转移的每一位可以分别贡献，所以考虑拆位。
把 \(g_u\) 写成 \(\sum_i 2^{i}f_{u,i,1}\)，\(f_{u,i,0/1}\) 设为 \(val\) 的第 \(i\) 位是 \(0/1\)，所有方案积的和，转移比较简单。
P5299 [PKUWC2018] Slay the Spire
假设已经摸出了 \(m\) 张牌，其中 \(c\) 张是攻击牌，\(m-c\) 张是强化牌。将其从大到小排序。
然后最佳的打出的方案一定是取前 \(k-t\) 张强化牌，剩 \(t\) 张攻击牌打出。
进一步的，因为强化牌每次至少 \(\times 2\)，而攻击牌递减，不可能达到 \(\times 2\) 的贡献，所以只出一张攻击。
考虑枚举 \(c\)，那么计算 \(c\) 张攻击牌中最大值的总和，以及 \(m-c\) 张强化牌积的和。
CF1530F Bingo
我们很显然能得到一个 \(O(2^{2n+2})\) 的容斥，枚举每个行/列/对角线的钦定情况，然后计算概率。
我们考虑先枚举行和对角线的钦定情况，然后快速计算列的答案。
注意到每个列的答案都是独立的，我们就不用容斥计算了，独立的意思是 \(P(A_1A_2)=P(A_1)\times P(A_2)\)。
其中 \(P(i)\) 表示第 \(i\) 列钦定放满的概率。那么，贡献是 \(\prod (1-P(i))\)。
可以 \(O(2^{n+2}n)\) 计算。需要高维前缀和优化。
AGC013E Placing Squares
一个朴素的容斥：设 \(f_i\) 表示到考虑了第 \(i\) 个限制点，合法的方案积的和。\(f_i=g_{pos_i}-\sum g_{pos_i-pos_j}\times f_j\)
其中，\(g_i\) 表示放 \(i\) 个位置方案积的和。\(g_i=\sum (i-j)^2g_j\)。然而 \(n,m\) 太大了，该做法不善。
考虑 \(a_i^2\) 的组合意义：把两个可区分的球放到 \(a_i\) 个可区分的盒子，允许一个盒子放多个的方案数。
题目被转化为：\(n\) 个数拆分为若干段，有 \(m\) 个位置不能分段，每个段里放两个球的方案数。
这样的话我们就可以设计一个 dp 了，设 \(f_{i,0/1/2}\) 表示当前段，已经放了 \(0/1/2\) 个球的方案数。
只有当已经放了 \(2\) 个球的时候我们可以开一个新的段。转移可以用矩阵快速幂来优化。
对于每个限制点之间我们都可以跑矩阵快速幂，时间复杂度 \(O(w^3m\log n)\)。
要注意的是两个球是不同的，转移到 \(1\) 的时候要带 \(2\) 的系数。
ARC100F Colorful Sequences
计算所有序列的 \(s\) 出现次数，其中序列一定存在一个长 \(k\) 的所有元素都出现的子区间。
如果不考虑序列合法的条件，拆贡献，枚举每个出现位置。那么答案就是 \(k^{n-m}(n-m+1)\)。
然后我们考虑容斥掉没有出现长 \(k\) 的所有元素都出现的子区间的贡献。
容斥仍然需要拆贡献，继续枚举 \(A\) 的每个出现位置，并计算不出现合法子区间的方案数。
三种情况：第一种，\(s\) 本身满足条件的，那么不需要容斥。
第二种，\(s\) 中含有重复元素的，那么肯定不存在包含 \(s\) 的子区间。
找到左边和右边极长子区间，我们只需要关注其大小 \(l,r\)，然后我们可以考虑 dp。
设 \(f_{i,j}\) 表示当前填了 \(i\) 个元素，当前极长的不同色连续段后缀大小为 \(j\)，已经不需要关注具体的元素。
转移是：\(f_{i,j}\to f_{i+1,1\sim i},f_{i,j}\times (k-j)\to f_{i+1,j+1}\)，可以采用后缀和优化。
第三种：\(s\) 中不含有重复元素，那么 \(m<k\)，可能会出现一个合法区间跨越 \(s\) 的情况。
因为我们不关心具体颜色，那么一个长度为 \(m\) 的不同色子区间是 \(s\) 的概率是 \((A_{k}^m)^{-1}\)。
所以我们已经无需拆贡献，在计算 \(f_{i,j}\) 的时候，我们顺便记录 \(g_{i,j}\) 表示当前状态下，期望有 \(s\) 的个数。
转移是相同的。
这题的话我们通过容斥以及拆贡献将元素都变为等价，才使得这题避免了状压。
P6478 [NOI Online #2 提高组] 游戏
这个题非常简单，然而因为状态设计错导致脑瘫。首先二项式反演。
然后我设的状态是 \(dp_{u,k,a,b}\) 表示 \(u\) 子树已经钦定了 \(k\) 对祖先关系，\(A,B\) 分别有 \(a,b\) 还没匹配。
实际上只需要设 \(dp_{u,k}\) 即可，考虑从 \(u\) 向子树某点连接转移，而子树里面 \(a,b\) 还剩多少个是已知的。
对于一个点对有两种考虑方式，孙子或祖先处考虑。这题我们只在其祖先处考虑。
状态设蠢的原因是因为我们是钦定多少个点对被选，而不是钦定哪些点对不选。
所以在孙子处，我们是无需关心其选或不选的。
如果没有二项式反演，我们的确需要像刚才那样子设状态。
而有了二项式反演呢？我们是无需关心除了钦定的点外的点的状态，子树里的所有点都可以被选。
ARC156D Xor Sum 5
通过观察题解注意到，\(C_{k}^c\bmod 2=[c\subset k]\)。
设 \(a_i\) 的出现次数是 \(c_i\)，贡献 \(C_{k}^{c_1,c_2,c_3}\) 是奇数时，\(c\) 是二进制下 \(k\) 的一个划分。
那么我们只需要知道 \(k\) 的每个二进制位被哪些 \(a\) 选了即可。
设 \(dp_{i,j}\) 表示当前考虑前 \(i\) 个二进制位，当前进位为 \(j\) 的方案数，如果 \(i\in k\)，那么枚举 \(a\) 加入 \(a\times 2^i\)。
考虑第 \(i\) 位什么时候做贡献，也就是当前位为奇数的方案数为奇数的时候。
但是 \(2|n\) 时如果 \(i\) 小于 \(k\) 的最高位，此时方案数无论如何都是 \(n\) 为偶数，是不做贡献的。
CF1612G Max Sum Array
完全不会这个题目。设一个元素出现的位置是 \(p_1,p_2,...,p_x\)，那么其贡献是 \(\sum_{i<j}p_j-p_i\)。
上式把每个项的系数拆开，也就是 \(\sum_{i} (2i-x-1)p_i\)。
考虑一个一个元素插入排列，相当于把每个位置的系数插入进去，显然系数递增时代价最大。
如果我们朴素地加入每个系数，设系数为 \(c\)，那么贡献是 \(c\) 的出现次数 \(+1\)，并使其出现次数 \(+1\)。
然而这样的话我们会导致把时间浪费在插入每个系数上。
其实我们只需要最后再算每个系数的贡献即可，是阶乘，考虑进行区间加，用差分数组即可。
P3266 [JLOI2015] 骗我呢
注意到：每行最多只有一个数没有出现过。那么不同的行只有 \(m+1\) 种：\(0\sim m\)。
考虑当前行是 \(i\) 没有选，那么下一行的不选的的数 \(j\) 需要满足 \(j\ge i-1\) 即可。
那么我们已经可以设计出一个 \(O(nm)\) 的 dp，现在呢我们考虑把问题转化为组合数学的模型。
设第 \(i\) 行不选的是 \(p_i\)，如果把第 \(i\) 行的 \(p_i\) 向右平移 \(i\)，那么，\(p_i\) 满足不降。\(p_i\in [i,i+m]\)。
所以假设我们知道了所有 \(p\)，那么我们按照大小顺序可以依次赋值给每个 \(p_i\)，可以用盒球模型。
考虑用网格图数路径的模型，相当于从 \((0,0)\) 开始向右或向上走，走到 \((n+m+1,n)\) 的方案数。
第一维增加 \(1\)，相当于 \(p\) 加 \(1\)；第二维加 \(1\)，相当于考虑完一行的 \(p\)。
总方案数是 \(C_{2n+m+1}^{n}\)，考虑容斥掉不合法的。有两种违法：\(y=x+1\) 以上的；\(y=x-m-2\) 以下的。
设两条直线为 \(A,B\)，那么减去第一次触碰 \(A\) 的和第一次触碰 \(B\) 的方案数即可。
第一次触碰 \(A\) 的方案数，直接把终点以 \(A\) 为轴轴对称过去，起点到新的终点的路径可以与之构成双射。
但是有个问题就是可能先经过了 \(B\)，所以我们要减去先经过 \(B\) 的，还是通过轴对称处理。
所以答案像 \(-A+BA-ABA+BABA\) 这样算即可。
CF1874E Jellyfish and Hack
明显 \(fun(p)\le n^2\)，所以我们可以设 \(f_{k,y}\) 表示长度为 \(k\) 的数组，值为 \(k\) 的方案数。
转移的话枚举第一位是第几大，然后做卷积合并，也就是 \(f_{k,y}=\sum_{p=1}^{k}C_{k-1}^{p-1}\sum _{t=0}^yf_{p-1,t}f_{k-p,y-k-t}\)。
考虑生成函数，设 \(F_k(x)=\sum f_{k,i}x^i\)，那么 \(F_k=x^k\sum_{p=1}^{k}C_{k-1}^{p-1}F_{p-1}F_{k-p}\)。
观察到：\(F_k\) 的系数不超过 \(\frac{1}{2}k(k+1)\)，这启示我们使用插值。
具体地，我们求出 \(F_k(x)\) 中 \(\frac{1}{2}k(k+1)\) 种 \(x\) 的答案后，就可以求出所有系数 \(f_{k,i}\) 的值。
枚举 \(x\)，然后 \(O(n^2)\) 的求出 \(F_k(x)\)，因为乘法是 \(O(1)\)，总复杂度 \(O(n^4)\)，最后插值回去 \(O(n^4)\)。
具体如何插值回去呢？因为 \(F_k(x)=\sum_{i}F_{k}(i)\prod_{j\neq i} \dfrac{x-j}{i-j}\)，积式后面分母容易算，把分子拿出来。
分子那里相当于做背包，可以做出一个多项式；然后运用退背包可以得到每个 \(i\) 的值，或者称大除法。
所以 \(F_k(x)=\sum_i F_k(i)\times H(i)\)，\(H(i)\) 是上面的那个多项式，然后对应次数的系数加起来。