从 2022-08-25 开始更新。
\(\mathbb{ARC \ 146 \ C}\)
观察
一眼递推，问题在于 \(\Theta(2^n)\) 的复杂度显然不对。
考虑怎么从上一层转移，可以从现在新增的元素里选出一些往上一层合法的集合中加，如果在添加后不合法则情况是上一层的集合存在一个大小为奇数的子集异或值和当前选出的元素相等，继续想，这个子集只可能有一个，因为如果存在两个，则上一层的该集合不合法，即会存在一个大小为偶数且异或和为 \(0\) 的子集。
其实还可以发现一个性质，即是说因为上一层的集合每一个大小为奇数的集合都对应着一个唯一一个不能加进去的元素，那么每一新元素都有 \(2^i - 2^{i - 1}\) 种选法。
具体推一下，定义 \(dp_i\) 为第 \(i\) 层的答案，那么可以拿到 \(dp_{i - 1}\) 。
得到的转移方程为
边界是 \(dp_1 = 1\) 。
回到最开始的问题，复杂度不对，其实打表可以看到在 \(i \ge n + 2\) 时，答案不会再次变化。
\(\mathbb{ABC \ 256 \ F}\)
/kk 因为这道题没看到弱智题 G
可以考虑一个最蠢的 \(dp_{t,i,j}\) 表示，前确定了 \(t\) 个维度后，距离 \(p\) 为 \(i\) ，距离 \(q\) 为 \(j\) 的多维体的总数，可以写出一个 \(\Theta(nD^3)\) 的转移方程。
然后比赛时就卡在这里了，，，
如果把代码写出来，估计优化就容易了。
for (int t = 1; t <= n; t++) {
memset(dp[t & 1], 0, sizeof(dp));
for (int pos = -2 * 1000; pos <= 2 * 1000; pos++) {
int dis1 = Abs(pos - p[t]);
int dis2 = Abs(pos - q[t]);
if (Max(dis1, dis2) > d) continue;
for (int i = 0; i <= d - dis1; i++) {
for (int j = 0; j <= d - dis2; j++) {
dp[t & 1][i + dis1][j + dis2] += dp[t & 1 ^ 1][i][j];
}
}
}
}
然后要搞一个奇妙的转化，定义 \(s_i = \mid p_i - q_i \mid\) ，把合法的 \((dis1,dis2)\) 分成三类。如下
\((s, 0), (s - 1, 1), (s - 2, 2), (s - 3, 3) \dots (0, s)\)
\((s + 1, 1), (s + 2, 2), (s + 3, 3) \dots\)
\((1, s + 1), (2, s + 2), (3, s + 3) \dots\)
那么这个就可以做了，因为这些合法的点均在一条直线上，最终可以优化到 \(\Theta(nd^2)\)。
\(\mathbb{ABC \ 264 \ G}\)
居然不会写了?
对于一个字符串，把转移看成在最后添加一个字符，则贡献只和最后两个字符有关，则可以直接建图跑最长路，顺带 \(spfa\) 判环即可。
\(\mathbb{ABC \ 232 \ F}\)
状压 + 逆序对
不难想到，两个操作可以分开考虑，可以视为首先把 \(\{A\}\) 变成 \(\{A'\}\) ，其中 \(\{A'\}\) 的数字可重集合和 \(\{B\}\) 等价。
看到数据范围很小，可以考虑状压，定义 \(dp_{sta}\) 表示把 \(sta\) 上为 \(1\) 的位数上的 \(A\) 数字放到 \(B\) 的前 \(cnt(sta)\) 位上的最小代价。
怎么转移呢，考虑向后填表，对于一个已知的状态 \(dp_{sta}\) ，要做的事是将 \(a_{j}\) 放到 \(b_{cnt(sta) + 1}\) 上，统计 \(sta\) 中在 \(j\) 之后的 \(1\) 的个数为 \(tot\)，那么转移就是 \(dp_{sta \otimes {2^j}} = dp_{sta} + tot \times y + \mid a_j - b_{cnt(sta) + 1} \mid \times x\) 。
\(\mathbb{ABC \ 236 \ F}\)
线性基
和 \(Kruskal\) 很相似。直接构造一个线性基，按代价从小到大依次往里面加。
\(\mathbb{ABC \ 237 \ F}\)
暴力 \(dp\)
定义 \(dp_{i, a, b, c}\) 为考虑到 \(ith\) 位，当前的 \(\mathrm{LIS}\) 序列为 \(\{a, b, c\}\) 。
转移时，考虑枚举下一位填入 \(j\) 并分类讨论，转移与 \(\mathrm{LIS}\) 相似。
\(\mathbb{ABC \ 239 \ F}\)
又一道构造
正向思考长时间无果，考虑什么样的连边会让整个图断掉，即是，存在两个连通块，都剩余 \(1\) 的度，结果这个两个块连在了一起，遂与外人间隔。
得到的提示是尽量把度数小的往大的上面连，但是还是有问题，比如 \(\{3, 2, 1, 1, 1\}\) ，会先将 \(3\) 个 \(1\) 往 \(3\) 上连，结果是 \(2\) 连不上去。考虑一个合并法，度数小的往次小的连，那么维护一个堆就可以解决。
\(\mathbb{ABC \ 244 \ F}\)
状压
定义 \(dp_{sta, u}\) 表示最后停在 \(u\) ，状态集合为 \(sta\) 的最短路。
转移则是枚举 \(u\) 的出边，得到 \(v\) ，下一次的状态则是 \(dp_{sta \otimes 2^v, v}\) 。发现这个转移是在 \(DAG\) 上进行的，那么直接建图跑 \(spfa\) 就行了。
\(\mathbb{ABC \ 246 \ F}\)
状压 + 容斥
怎么这么多状压题。。。
开始想了很久，因为没有看到所有字符串是 abcdefghijklmnopqrstuvwxyz 的子序列。
那么直接考虑整个字符串是由哪几个拼起来的，现在的问题就变成了对于给定的一堆字符串拼成一个长度为 \(l\) 的有多少种方案。
额，发现不对。。。先放了。
\(\mathbb{ABC \ 247 \ F}\)
并查集 + dp
这和原来做的 \(cf\) 上的一道题很想，也是关于构造二分图的方案数。
很容易想到二分图，那么每个连通块的方案数乘起来就是总方案数。
考虑怎么求每个连通块的总方案数，问题现在是对于一个二分图，要选择一些边使得每个点都有覆盖，定义 \(dp_{i}\) 表示第 \(i\) 条边选不选的方案数，则 \(dp_{i} = dp_{i - 1} + dp_{i - 2}\) ，边界条件可以手玩得出。
\(\mathbb{ABC \ 249 \ F}\)
细节
思路很好想，可以发现操作 \(1\) 是具有一键抹销功能的，只有最后一个操作 \(1\) 和之后的操作 \(2\) 构成的操作有影响。
考虑钦定最后一个操作 \(1\) ，那么用一个堆维护之后的操作就可以了。
\(\mathbb{ABC \ 251 \ F}\)
点破
乍一看很高级，是个构造，其实点破之后很简单，操作 \(1\) 要求祖先和子孙之间有虚边，操作 \(2\) 要求，兄弟间有虚边，那么用 \(dfs\) 和 \(bfs\) 分别求一次生成树就可以了。
\(\mathbb{ABC \ 252 \ F}\)
贪心典
合并果子逆向版。
\(\mathbb{ABC \ 266 \ F}\)
简单期望
定义 \(dp_{i}\) 为走到第 \(i\) 步的最大期望，转移很简单， \(dp_{i} = \sum_{j = 1}^{6}\frac{\max\{j, dp_{i - 1}\}}{6}\) 。
\(\mathbb{ABC \ 223 \ E}\)
想了好久。。。?
其实很简单，但我一开始以为是个贪心，构造了很久都没弄出来。
首先考虑两个矩形的情况怎么做，设面积分别为 \(S_1, S_2\)，问题转化为在大的平面上划一条线，分成两个部分，能分别放下两个矩形。
如果该直线与 \(x\) 轴平行，则 \(l = \lceil \frac{S_1}{x} \rceil\) ，换成 \(y\) 轴也同理。之后再将其中一个矩形继续划分就可以判定了。
\(\mathbb{ABC \ 233 \ F}\)
码码码
应该算个原题，一眼线段树，在每个节点上维护当前节点上失配的 左 / 右 括号数，合并就用右儿子的右括号去补全左儿子的左括号，交换操作可以看成单点修改。
\(\mathbb{ABC \ 233 \ G}\)
marked
题面很漂亮，给定一棵树，问有多少个节点满足：删去这个节点后的图的匹配数等于原树的匹配数。
首先重新想一下图匹配的定义：即是在一张图中，两两没有公共点的边集数。一个结论是匹配数等于点数减去最大独立集。
最大独立集是可以直接树形 dp 不带任何技巧地求出来的，那么考虑删点怎么处理。
首先从已知的数据出发，现在已经得到的是 \(u\) 的子树内的最大独立集的大小，这一部分数据还要和 \(u\) 的子树外的数据合并。
首先定义出来 \(f_{u, 0/1}\) 表是当前点选不选的子树内的最大独立集大小， \(g_{u, 0/1}\) 表示在不考虑当前点的子树情况下当前点的父亲选不选的最大独立集大小。
那么简单的换根 dp 就可以解决了。首先记 \(sum_1 = \sum_{v \in fa} \max \{ f_{v, 0}, f_{v, 1} \}, sum_2 = \sum_{v \in fa} f_{v,0}\) ，最后的转移方程为
\(\mathbb{ABC \ 222 \ E}\)
转化
需要一个转化，首先统计每条边出现的次数，记为 \(cnt_i\) , 记 \(S = \sum_{i = 1}^n cnt_i\) 然后可以类似于一个解方程转化，已知了 \(R + B = S, R - B = k\) ，则 \(R = \frac{S + k}{2}\) ，这个是一个定值，那么问题就转化为选或不选一些边，使总数和为 \(\frac{S + k}{2}\) 。这个就可以简单地用背包 \(dp\) 解决。
结果写挂了一发，想了半天没看出错，遂改了一个写法，莫名其妙就过了。
\(\mathbb{ABC \ 222 \ F}\)
结论
首先观察发现，其实可以建 \(n\) 个虚点，建边为 \((i, i + n, d_i)\) ，这样就把额外的点权转化成了只需要考虑边权。
问题就变成了求树上任意一点的最远的点，一个远古结论是这个最远点一定为树的两个端点之一。那么两遍 \(dfs\) 就可以解决。
坑点在于题目自身还有一个限制 \(\max_{1 \le j \le N, j \not = i} E_{i, j}\) ，也就是说不能连向自己对应的虚点，特判即可。
\(\mathbb{ABC \ 217 \ F}\)
一个典型的区间 dp
但是我把题读错了。。。想了 \(15min^+\) 才感觉不对。
合并的时候注意组合数系数。
\(\mathbb{ABC \ 267 \ G}\)
第一步就想错了。。。
想不到就是想不到，第一步应该排序。
排序之后考虑不是生成排列，而是一个一个把数插进去，则可以写出式子 \(dp[i + 1][j + 1] = dp[i + 1][j + 1] + dp[i][j] * (i - cnt - j) \\ dp[i + 1][j] = dp[i + 1][j] + dp[i][j] * (cnt + j + 1)\) ，其中 \(cnt\) 表示当前已经和 \(a_i\) 相等的数的个数。
\(\mathbb{ABC \ 268 \ F}\)
5 min
感觉很能贪心，记 \(val_i\) 为第 \(i\) 个字符串中所有数字的和， \(num_i\) 为第 \(i\) 个字符串中的 \(X\) 的个数，那么只要 \(num_x \times val_y > num_y \times val_x\) 就认定为 \(x\) 放在 \(y\) 前面会更优。
\(\mathbb{AGC \ 058 \ B}\)
支配 ?
首先可以想到对于一个 \(p_i\) 他能够支配的区域是 \([l, r]\) 使得 \(p_j \le p_i, j \in [l, r]\) ，那么很简单的 \(dp\) 方程可以写成 \(dp_{j} = (dp_{j} + dp_{j - 1})\)
\(\mathbb{ABC \ 273 \ F}\)
又不会区间 dp 了
定义 \(dp_{l, r, 0/1}\) 表示走完了 \([l, r]\) 现在处于 \(l/r\) 中一个端点，注意其中的 \(l, r\) 是离散化后的点，并且表示下标。
一开始觉得要分类讨论，其实不然。
可以把捡锤子，和砸墙看成一种操作。
得到 \(dp_{l, r, 0} = \min\{dp_{l + 1, r, 1} + pos_r - pos_l, dp_{l + 1, r, 0} + pos_{l + 1} - pos_{l} \}\)
\(\mathbb{ABC \ 273 \ G}\)
又是一个一个数矩阵问题啊啊
无解直接判行列是否相等就行了。
以为是个组合数学，但思考无果，选择直接 \(dp\) 。
定义 \(dp_{i, j, k}\) 表示计算到第 \(i\) 行，在 \(j, k\) 个列上放了 \(1, 2\) 的方案数，考虑转移。
\(\mathbb{ABC \ 274 \ F}\)
直接模拟
有个东西叫做相对位移，所以枚举每条鱼，以它为原点，固定不动，可以轻松地知道每条鱼在 \([0, a]\) 的时间段，那么线段树搞搞就行了，复杂度 \(\Theta(n^2 \log n)\) 很可以过。
\(\mathbb{ABC \ 274 \ G}\)
烂 trick
行列连边二分图的烂 trick ，只不过多了障碍物，对于一段横竖没被阻断的看成一块，重新编号后行列连边就行。跑二分图过不了，网络流就行。
\(\mathbb{ABC \ 275 \ F}\)
BOT CJG 永远不会把顺序无影响的操作问题看成一个可以从左往右直接 dp 的 easy task
\(dp\) 直接上，定义 \(dp_{i, j}\) 表示考虑到了第 \(i\) 个数，现在总和为 \(j\) 的最小代价。
当不删 \(i\) 时，\(dp_{i, j} = dp_{i - 1, j - a_i}\) 。如果要删 \(i\) ，则需要枚举一个左端点 \(k\) ，\(dp_{i, j} = \min \{ dp_{k,j} \} + 1\) 。
可以做到 \(\Theta(nm)\) 直接过。
\(\mathbb{ABC \ 276 \ G}\)
开始数数哦，原来给序列做差分可以把每个数的值域变成序列和的值域
看到求合法单调序列个数，想到转化成求其差分序列个数，这是等价的。
定义 \(B\) 为 \(A\) 的差分序列，则 \(\sum b_{i} = M, \forall b_{i}, i \ge 2, b_{i} \mod 3 \equiv 1 / 2\) 。
一个处理同余的手法是把式子写成带余除式，即 \(b_i = 3y_i + x_i\)，发现对于每个 \(b_i\) 均是独立的，等价地得到 \(x_i, y_i\) 也是独立的，那么在和的限制下计数就可以了。
\(\sum 3y_i + x_i = M\)， 移项，改写成 \(x, y\) 的互相的限制，即 \(\sum y_i \le \lfloor \frac{M - \sum x_i}{3} \rfloor\) 。
这个时候分开计算 \(x, y\) 。
\(\sum y = N\) 的方案数为 \(\binom{N + y - 1}{n - 1}\) 。
对于 \(x\) 因为取值固定，枚举个数计算贡献就可以了，注意要把 \(x_1\) 单独拎出来。
\(\mathbb{ABC \ 279 \ F}\)
并查集水题，略。
\(\mathbb{ABC \ 279 \ G}\)
直接做？
定义一个线性表示答案的 \(dp_{i, 1/2}\) ，\(dp_{i, 1} = dp_{i - k + 1, 1}, dp_{i, 2} = dp_{i - k + 1, 1} \times C + dp_{i-k+1,2}\times 2\)
\(\mathbb{ABC \ 280 \ F}\)
性质发现
由于这张图的特殊构造，可以尝试发现性质，如果一个连通块中有正环，则答案为 inf ，否则两点间路径唯一，那么钦定一个节点遍历整个连通块，处理距离，两点距离的差即为答案。
\(\mathbb{ABC \ 280 \ G}\)
如何优化？
两个点之间距离的计算比较复杂，但是发现距离具有平移不变的性质，于是考虑通过每个点与 \((0,0)\) 之间的距离来刻画两点间的距离。
具体过程可以手玩得到，记 \(d_1 = x_1 - y_1, d_2 = y_1 - y_2\)两点间的距离为 \(\max\{\mid d_1 \mid, \mid d_2 \mid, \mid d_1 - d_2 \mid\}\) 。
发现这个东西是三维的，于是可以用一个 \(d^3\) 的正方体刻画，那么每次框起来的就是一个可行的点集，考虑去重。
于是开始枚举每一个维度上的最小值，记为 \(x_0, y_0, z_0\) ，钦定这些点必须选，如果这些点围起来的点数为 \(tot\) ，则总的答案增加 \(2^{tot}\) ，直接做是 \(\Theta(n^4)\) 的，在统计围起来的点数是可以用双指针优化，最后的复杂度是 \(\Theta(n^3)\) 。
\(\mathbb{ABC \ 281 \ F}\)
经典
比较经典了，首先可以把字典树建出来，然后在字典树上做树形 \(dp\) ，具体来说，定义 \(dp_u\) 为使用 \(u\) 子树内的点构成的数列来计算得到的答案，当只有一个子节点时，可以直接继承，否则选择小的一个加上 \(2^i\) 往上算。
\(\mathbb{ABC \ 281 \ G}\)
Spanning Tree?
图的计数问题要注意一些定理的使用和从生成树的角度思考，看到题目中有对于距离的限制，考虑把每一层分开，使得 \(1\) 在最深的一层，那么此时计数就简单了，定义 \(dp_{i, j}\) 表示用了前 \(i\) 个点，后面的 \(j\) 个点分在一层时的方案数，主要到并没有考虑现在是第几层，因为计数的原则只要是问题答案等价且转移后的状态合法就可以了，那么转移就变成了当前层自身连边和向上一层连边，方程是
\(\mathbb{ABC \ 277 \ G}\)
直接去掉
考虑一个最简单的 \(dp_{u, j, l}\) 表示走到 \(u\) ，步数为 \(j\) ，此时等级为 \(l\) 的概率，转移是 \(dp_{v, j + 1, l + c_v} = dp_{v, j + 1, l + c_v} + dp_{u, j, l} \times \frac{1}{deg_u}\) 。
复杂度是 \(\Theta(n^3)\) 的，考虑降维，从这三维对答案的贡献来看，最终统计时，一个点的贡献是 \(\sum_{l = 0}^{k} dp_{u, j, l} \times l^2\) ，变量是 \(l\) ，即是最后一维，因为 \(i, j\) 是特征量，不能去，那么只能把 \(l\) 优化掉。在转移过程中 \(l\) 的变化只有 \(+1\) 的操作，做完之后一个点的贡献变为 \(\frac{1}{deg_u} \times \sum_{l = 0}^{k} (l+1)^2\) ，因为系数是统一的，那么直接维护二次的增量就可以了。
\(\mathbb{ABC \ 272 \ G}\)
就随机
考虑从集合里面抽出来两个元素，则他们两个差有一定概率是这个 \(M\) ，这取决于这两个数是不是在这个模意义下相同的集合，很明显，如果 \(M\) 满足条件，则 \(M\) 的因数也满足，那么就用这个差值和这两个数去掉余数之后的值做差就可以了。
如果全部枚举则检验复杂度是 \(\Theta(n^3)\) 的，因为这个东西性质很强，我们每次抽取两个元素，都在满足要求的集合里面的概率最小是 \(\frac{1}{4}\) ，那么多随几次就行了。
\(\mathbb{ABC \ 271 \ G}\)
矩阵 /se
神奇，网上题解都怎么一步到位的。。。
定义第 \(t\) 次访问是在 \(i\) 点，要转移到下一次时只需要考虑是几点就可以了，但是这里面有个小问题，你不知道中间间隔了多少天，为了方便，记从 \(i\) 到 \(j\) 没有人访问的概率是 \(f_{i, j}\) ，那么从 \(i\) 转移到 \(j\) 的概率是 \(\sum_{n=0}^{\infty}f_{1, 24}^n \times f_{i + 1, j - 1} \times p_i\) ，发现这个是等比求和，则概率是 \(\frac{f_{i + 1, j - 1} \times p_i}{1 - f_{1, 24}}\) 。
然后矩阵快速幂去算即可。
\(\mathbb{ABC \ 270 \ G}\)
整无雨了
考虑翻一次的贡献是 \(B_i - A_i\) ，值域很小，直接二进制背包 \(dp\) 。
\(\mathbb{ABC \ 283 \ G}\)
板子题
赚翻了，这个是线性基的板题。
\(\mathbb{ABC \ 283 \ E}\)
这应该是近几次最难的 E \doge
用和炮兵阵地一样的思路就可以解决了，枚举上一行和这一行的状态直接进行 \(dp\) 。
\(\mathbb{ABC \ 283 \ F}\)
用拆绝对值搞过去的，记录一下最小生成树做法
也很简单，把 \((i, p_i)\) 看成二维平面上的点，距离的定义就是曼哈顿距离，然后求曼哈顿最小生成树，结论是每一个点每四十五度只会连出去一条边。但其实最后的方法都会回到按一维排序，然后另一位用数据结构。
\(\mathbb{ABC \ 283 \ Ex}\)
类欧！
比较懒，赛时写了个 \(G\) 就去补其他题了，所以是口胡 \(Ex\) 。
因为答案每一位独立，那就把每一位拆开，对于一个数 \(x\) ，二进制下第 \(k\) 位是 \(1\) ，\(2^k \le x \mod 2^{k+1} < 2^{k+1}\) ，\(\frac{x+2^k}{2^{k+1}} -\frac{x}{2^{k+1}} = 1\) ，这三个条件是等价的。
那么直接用最下面的形式求解就可以了，复杂度是 \(\log n\) 。
\(\mathbb{AGC \ 060 \ B}\)
拐角
一个比较自然的想法是在经过的路径上全部都赋值为 \(0\) , 考虑怎么使这条路径成为唯一的，那么需要注意到拐角处，不能出现一样的数字，否则可以出现一条新的路径，那么每个转角都需要一个新的数字，统计拐角个数即可。
\(\mathbb{AGC \ 060 \ C}\)
很妙（但是暂时咕掉）
首先需要考察这两个位置的特点，既然题目是以堆为背景，那就把大根堆建出来，\(2^a\) 是指的 \(a+1\) 层的第一个数， \(2^b-1\) 是指的 \(b\) 层的最后一个数，所求的就是前一个位置上的数比后一个位置上数小的概率，因为所有的排列数很容易得到，那么对合法的排列计数即可。
考虑怎么去在堆上刻画大小关系，其实就是用拓扑排序，生成排列，满足先后关系，令 \(dp_{u, v}\) 表示，在深度为 \(u, v\) 的两颗满二叉树上走，先访问到 \(2^a\) 的概率。
\(\mathbb{AGC \ 035 \ D}\)
时空倒流
注意到倒着把数字加入到序列里和正着删数是等价的。
定义 \(dp_{l, r, x, y}\) 表示在 \(l, r\) 这段区间里面，左边的 \(a_l\) 被算了 \(x\) 次，右边的 \(a_r\) 被算了 \(r\) 次的最小代价。
那么转移是 \(dp_{l, r, x, y} = \min \sum_{p=l+1}^{r-1} dp_{l, p, x + y, y} + dp_{p, r, x, x + y} + a_{p} \times (x + y)\) 。
\(\mathbb{AGC \ 059 \ C}\)
从简单情况开始手玩
从 \(3\) 个数 \(a, b, c\) 开始思考，什么情况下 \((a, c)\) 的询问会无效。
即是说 \((a, c)\) 在询问前就已知了一条链将其联通。对于每一个三元组 \((a, b, c)\) ，如果最后出现的询问是 \((a, c)\) ，要其合法，那么 \(b\) 的值不能处在 \(a, c\) 的中间。
现在就可以拿到每一个三元环 \((a, b, c)\) 中的关系了，即是说 \(a\rightarrow b\) 和 \(c\rightarrow b\) 必须同向，于是把边压成点，跑种类并查集求出连通块的个数 \(k\) ，最后答案即是 \(2^k\) 。
\(\mathbb{AGC \ 039 \ E}\)
《简单区间 dp》 | 从限制入手
可以描述为 \(3\) 个限制条件，不成环，联通， \(n\) 组匹配。
考虑从匹配入手，将匹配数作为 \(dp\) 的维度，定义 \(dp_{l, r}\) 表示 \([l, r]\) 区间里面完成限制的方案数，发现相邻两个区间无法合并，少考虑了匹配数的限制，那么再加上一维 \(i\) ，定义 \(f_{l, r, i}\) 表示在 \([l, r]\) 区间里满足限制且用 \(i\) 向外连边的方案数，类似地，定义 \(g_{l, r, i}\) 表示区间外一点 \(i\) ，向区间 \([l, r]\) 内连边的方案数。
转移时，先枚举要转移到的区间 \([l, r]\) ，\(cnt = \sum g_{l, j, i} \times f_{k, r, i}\) ，注意还要更新 \(f_{l, r, i} = \sum_{j + 1, k - 1, i} f_{j, k, i}\) 。
\(\mathbb{ARC \ 153 \ E}\)
菜是原罪
考虑正向构造是可以直接贪心做的。
对于每一个 \(a_i\) ，如果 \(a_i\) 小于当前字符串的头部的值，则直接放在开头，否则放结尾。
那么定义 \(dp_{l, r}\) 为生成 \([l, r]\) 这个区间的方案数，确切地转移为 \(dp_{l, r} = dp_{l + 1, r} \times [a_l \le a_{l + 1}] + dp_{l, r - 1} \times [a_l < a_{r}]\)。
至于为什么一个是 \(<\) 一个是 \(\le\) 原因是当 \(a_{l}\) 和 \(a_{r}\) 或 \(a_{l + 1}\) 相等时会算重。
到此处可以有 \(\Theta(n^2)\) 的做法了，其实可以用卷积一类的东西做到 \(\Theta(n \log n)\) ，但是不会了。
\(\mathbb{ARC \ 154 \ A}\)
。
贪心换，小的全放 \(A\) ，大的全放在 \(B\) 。
\(\mathbb{ARC \ 154 \ B}\)
基础方法
发现操作等价于把前面 \(k\) 个拿出来随便插，那么直接判断后面的是否是 \(s\) 的子串就可以了，套二分就可以过了。
\(\mathbb{ARC \ 154 \ C}\)
不是很理解
直接模拟即可。。。
\(\mathbb{ARC \ 154 \ D}\)
interesting
这个交互有点意思，我们可以首先把 \(1\) 的位置用 \(n\) 次问出来。
问出来之后就可以 stable_sort 排序直接过了。
\(\mathbb{ARC \ 154 \ E}\)
发掘性质！单点！改写！
首先改写这个贡献的式子
假设我已经拿到了最后的序列，那么根据定义，每个点的贡献是
考虑这个贡献用动态的方式呈现，首先这个序列有序，对于一个位置 \(i\) ，将他右边的一个数 \(j\) 放在前面去，这个位置变成 \(i + 1\) ，此时贡献是让 \(g(i)+1\) ，反之，放一个左边的到后面去，位置变成 \(i - 1\) 贡献 \(g(i) - 1\) ，那么可以得到 \(g(i)=i(i - Q_i)\) 。
那么此时计算 \(Q_i\) 在某个位置上的期望就可以了，很容易发现，这个期望很对称，将 \(Q_i\) 放在 \(i\) 和放在 \(n - i + 1\) 这两个位置上的方案数相同，那么最后位置的期望就是 \(\frac{n + 1}{2}\) 。
\(\mathbb{ABC \ 287 \ E}\)
trie板题
\(\mathbb{ABC \ 287 \ F}\)
比较经典
定义 \(dp_{u, i, 0/1}\) 表示以 \(u\) 为根的子树被划分成 \(i\) 个块，\(u\) 节点本身选不选的方案数，树形 \(dp\) 即可。
\(\mathbb{ABC \ 287 \ G}\)
线段树上二分
rt.
\(\mathbb{ARC \ 155 \ B}\)
re 导致的 wa
观察这个式子 \(f(x) = \mid \mid x - a \mid - b \mid\) 可以拆成 \(\min \{ x - (a + b), x - (a - b) \}\) 。
这个形式直接用 set 维护就可以了，结果 upper_bound 找到了 end ，一波 *it 直接 GG。
\(\mathbb{ARC \ 155 \ C}\)
反复往后跳，双向关系
看到操作使两个序列相等，注意到是否有双向关系。
因为不要求步数，那么构造使得两个序列变成同一个形式就可以了。
首先考察发现只有 ooe 和 eee 这两种形式可以区间改序，并且发现这个可以有传递的可能，什么意思呢。
对于下面这个情况 ooeeeeeeeee 我们可以把最前面的两个 o 反复操作，让 oo 到最后面去，并且可以发现，我们可以把所有的 o 全部转移到后面去，最后的形式大概是 eeeeoeoooooo ，为什么中间要嵌入一个 e 呢，因为我们可以利用这个 e 使得后面的所有的 o 和前面的 e 全部改序。
那么直接模拟这个过程就可以了。
\(\mathbb{ARC \ 155 \ F}\)
E, F 先咕着，做一些多项式题，这篇题解是我人工翻译的
[1] Double Counting 双重计数
考虑从叶子节点开始，用唯一的方式（如果有的话）来构造出一棵满足条件的树。因此，我们可以对一棵每个节点度为 \(D_i\) 的有向有标号树来代替无向树进行计数。
常用的对有标号树计数的方式是双重计数，设 \(A\) 是原问题的答案，\(B\) 是这棵有根树的数量，其中
- 树根是 \(N\) 个节点中任意一个。
- 从节点 \(i\) 连出的 \(D_i\) 条边用 \(1\) 到 \(D_i\) 标号。
那么，\(B=A \times N \times \prod_{i=1}^{N}D_i!\) 。
[2] Construction of the rooted trees 有根树的构造有根树可以按照一下方法构造，此外对于所有的树，按以下方式都有唯一构造。
- 确定与根相连的节点集合 \(S\) 。
- 对于 \(S\) 中的节点，从 \(D_i\) 中选择一条指向根，并给其他的边选择指向的节点。
- 确定其他边的终点。
考虑在完成了第一步和第二步之后，执行第三步的方式有多少，让我们按节点编号的升序，边的升序来开始考虑，可以选择没有父节点且与当前起点不在一个连通块里的点作为终点。在一开始，有 \(n - \mid S \mid\) 个节点没有父节点，所以有 \((n - \mid S \mid - 1)!\) 种方式，特别地，这一步的方案数和上一步无关。
接下来，来计算第二步的方案数。这里有 \(\prod_{i \in S} D_i\) 种方式选择指向根的边，对于其他边的终点的方案数，观察可以得到这个方案数等于 \(N\) 个节点 \(\mid S \mid\) 条边组成森林的方案数。
现在，我们把选出来的 \(S\) 忽略掉，从 \(N\) 个节点和 \(0\) 条边开始，重复以下操作 \(\mid S \mid\) 次，形成一个有根森林。将一个节点 \(u\) 与另一个在其连通块之外的没有父节点的 \(v\) 连接。这里有 \(\prod_{i = 1}^{\mid S \mid} N \times (N - i) = N^{\mid S \mid} \times \frac{(N - 1)!}{(N - \mid S \mid - 1)!}\) 来选择 \(u\) 和 \(v\) ，然后消序得到 \(N^{\mid S \mid} \times \frac{(N - 1)!}{\mid S \mid!(N - \mid S \mid - 1)!}\) 种方案。对称地来看，其中一共有 \(N^{\mid S \mid} \times \frac{(N - 1)!}{\mid S \mid!(N - \mid S \mid - 1)!} \times \frac{1}{N^C \mid S \mid} = N^{\mid S \mid}(N - \mid S \mid)\) 种方案满足所选出来的父节点集合为 \(S\) 。
因此，在第一步钦定了 \(S\) 之后，这里有 \(N^{\mid S \mid - 1} \times (N - \mid S \mid) !\times \prod_{i \in S} D_i\) 棵满足条件的有根树可以被构造出来。
[3] Using convolution 使用卷积
故而，我们定义 \(f(x) = \prod_{i}^{N}(1 + D_ix)\)，我们有 \(B = \sum_{k = 0}^{N - 1}N^{k - 1} (N - k)[x^k]f(x)\) 。于是就可以用多项式直接做了。
\(\mathbb{AGC \ 009 \ C}\)
首先根据相邻三个数的关系判无解。
直接定义 \(dp_i\) 表示第一个集合最后一个数选择的是 \(i\)，并且钦定 \(A > B\)，考虑转移，只需要找到 \(j\) 满足 \(a_j + A \le a_i, \forall x<y \in (j, i) \ a_x + B \le a_y\) 即可。
发现这样可行的 \(j\) 一定是一段连续的区间，所以双指针前缀和转移可以做到 \(\Theta(n)\)。
\(\mathbb{AGC \ 043 \ B}\)
人类智慧题，但是不难。
观察到答案一定在 \(0,1,2\) 中出现，所以判断是哪一个就行了，因为绝对值不影响奇偶性，所以可以直接 Lucas 判断奇偶性，如果是奇数就是 \(1\)，现在的目标是区分 \(0,2\)，不难想到把 \(2\) 全部变成 \(1\)，再按上面的方法判断一下，如果是奇数就是 \(2\)，否则是 \(0\)。
\(\mathbb{AGC \ 043 \ D}\)
需要手玩，如果画成柱状图大概是
发现分布很有规律，有连续的单调的段，长度 \(len \in [1,3]\)，并且每段的开头放在一起单调不降，长度为 \(2\) 的段数量永远小于长度为 \(1\) 的段。
考虑为啥会出现这种情况，对于原序列一段 \(A_1, A_2, A_3\)，如果 \(A_1 > A_2\) 或者 \(A_2 > A_3\)，那么这三个数会有两个连续被取出；如果 \(A_1 > A_2\) 并且 \(A_1 > A_3\)，这三个数会一起取出。
上述一起取出来的数一定会被扔进一个单调的块里面，因为大小为 \(2\) 的块和大小为 \(1\) 的块都会成对出现，所以大小为 \(2\) 的块的个数一定小于等于大小为 \(1\) 的块的个数。
于是定义 \(dp_{i, j}\) 表示现在长度为 \(i\)，大小为 \(1\) 的块的个数减大小为 \(2\) 的块的个数为 \(j\) 的方案数，可以直接转移。
\(\mathbb{AGC \ 052 \ C}\)
很抽象，等会儿写。
\(\mathbb{ABC \ 214 \ G}\)
如果是单独的一个序列，直接错排即可，这道题尝试建图，把 \(p_i\) 和 \(q_i\) 连起来。
发现每个点至多两个度，所以最后得到的图由很多环或者单链拼接而成，每一条边都对于序列中一个数，不合法的情况便是这个数选择了这条边两端连接的两个点之一。
回到错排的做法，需要钦定某些位置不合法，尝试在这道题使用该方法，定义 \(f_i\) 表示至少有 \(i\) 个数错位的方案数，定义 \(g_i\) 表示恰好有 \(i\) 个数错位的方案数，得到
发现每个环都互不影响，贡献只于环的大小相关，于是拉出来考虑每个环如何算。
对于一个大小为 \(c\) 的环，要使它错位 \(k\) 个位置，方案数为 \(\binom{2c - k}{k} + \binom{2c - k - 1}{k - 1}\)。
然后暴力卷积拼答案即可。
\(\mathbb{AGC \ 025 \ B}\)
很快啊，把绿看成红加蓝，变成涂了一种颜色的可以继续涂。
\(\mathbb{AGC \ 022 \ F}\)
nKessi 快来教我?。