\(\text{By DaiRuiChen007}\)
1. [ARC162E] Strange Constraints
给定 \(a_1\sim a_n\)，求有多少 \(b_1\sim b_n\) 满足：
- \(b_i\in [1,n]\)，且 \(i\) 和 \(b_i\) 的出现次数均不超过 \(a_i\)。
数据范围：\(n\le 500\)。
设 \(\ge k\) 的 \(a_i\) 有 \(c_k\) 个。
显然要把同一个颜色一起插入，假设该颜色出现次数为 \(p\)，那么可选的值有 \(c_p\) 种，位置也有 \(c_p\) 个，这是容易的。
假如要插更多颜色，只要我们按出现次数从大到小插，那么每个被占用过的位置和值都在这 \(c_p\) 个数里出现过，只要记录插的颜色数和大小和。
因此 \(dp_{i,j,k}\) 表示出现次数 \(\ge i\) 的颜色共有 \(j\) 个，总占用空间为 \(k\) 的方案数，转移时枚举出现次数为 \(i\) 的颜色数 \(x\)，\(dp_{i,j,k}\gets dp_{i+1,j+x,k+ix}\)，系数是一堆组合数分配位置和值。
注意到 \(ij\le n,ix\le n\)，因此枚举 \(i,j,x\) 复杂度是 \(\mathcal O(n^2)\) 的。
时间复杂度 \(\mathcal O(n^3)\)。
2. [ARC162F] Montage
对于一个 \(n\times m\) 的 \(01\) 矩阵 \(A\)，其合法当且仅当：
- \(\forall 1\le i<j\le n,1\le x<y\le m\) 有 \(A_{i,x}\times A_{j,y}\le A_{i,y}\times A_{j,x}\)。
求有多少合法矩阵。
数据范围：\(n,m\le 400\)。
显然全 \(1\) 矩阵合法，考虑把某个位置 \((i,j)\) 变成 \(0\)。
那么对于所有 \(x\ge i,y\le j\)，\(A_{x,j}\times A_{i,y}=0\)，那么 \(A_{i+1,j}\sim A_{n,j}\) 和 \(A_{i,1}\sim A_{i,j-1}\)，至少有一个部分全是 \(0\)（即左侧射线和下方射线）。
同理 \((i,j)\) 的上方射线和右侧射线至少有一个全是 \(0\)。
如果把 \((i,j)\) 的上方射线和下方射线全部变成 \(0\)，直接变成了 \(n\times m-1\) 的子问题，这种操作是平凡的。
那么我们只要考虑所有 \(i\times j\) 的非平凡合法矩阵，乘以 \(\binom ni\times\binom mj\) 作为系数即可。
对于一个非平凡的矩阵，不妨假设清零的是上方射线和左侧射线。
由定义，对于 \((i,j)\) 上方的每个点，其下方至少有一个 \(1\)，那么他们的左侧射线必须全是 \(0\)，那么 \(x\le i,y\le j\) 的所有 \(A_{x,y}=0\)。
因此每个 \(0\) 会导致其左上方或右下方全部被清 \(0\)。
所以每行的 \(1\) 必须连续，设第 \(i\) 行区间为 \([l_i,r_i]\)，显然 \(l_i\le l_{i-1},r_i\le r_{i-1}\)。
由于不能有全零的行或列，那么 \(r_1=m,l_n=1\)，且 \(r_i\ge l_{i-1}-1\)。
设 \(f_{i,l,r}\) 为第 \(i\) 行区间为 \([l,r]\) 的方案数，显然转移是对一个矩形区域 \(+f_{i,l,r}\)，二维前缀和优化即可。
时间复杂度 \(\mathcal O(nm^2)\)。
3. [ARC163D] Sum of SCC
给定 \(n\) 个点，求恰有 \(m\) 条顺序边（\(u\to v\) 且 \(u<v\)）的所有竞赛图的强连通分量数量之和。
数据范围：\(n\le 30\)。
显然竞赛图缩点形成链，链上每条边恰好对应一个割使得所有边都是 \(S\to T\)。
那么链的点数就是 \(S\ne \varnothing\)（可以 \(S=V,T=\varnothing\)）的割数量总和。
直接 dp，设 \(f_{i,j,k}\) 表示 \([1,i]\) 中 \(|T|=j\)，且此时 \(S\to T\) 的边中恰好有 \(k\) 条顺序边。
转移为：\(f_{i,j,k}\to f_{i+1,j,k}\) 和 \(f_{i,j,k}\to f_{i+1,j+1,k+i-j}\)。
最后答案就是 \(\sum f_{i,j,k}\binom{n\times (n-1)/2-j\times (n-j)}{m-k}\)。
数据范围：\(\mathcal O(n^4)\)。
4. [ARC163E] Chmin XOR Game
给定 \(a_1\sim a_n\)，每次操作选定 \(x\)，然后令 \(a_i\to \min(a_i\oplus x,a_i)\)（至少要令一个数减小）。
两人轮流操作，不能操作者输，求谁获胜。
数据范围：\(n\le 100\)。
先打表 \(n=2\) 的情况（设 \(a>b\)），对于值域 \([0,4)\) 的问题，当且仅当 \(a=b>0\) 或 \(a>b=0\) 时先手胜。
进一步发现一般的情况当且仅当，四进制下某一位满足这个限制，那么先手胜：
如果先手面对一个必败局面，枚举容易证明，考虑 \(x\) 的非零最高位，无论怎么操作都会转移到必胜局面。
否则我们找到最高的合法位 \((a_i,b_i)\)：
- 如果 \(a_i=b_i>0\)，那么取 \(x_i=a_i\)，显然 \((a,b)\gets(a\oplus x,b\oplus x)\)：
- 如这一位后手胜，直接取 \(x_j=0\)。
- 如果 \(a_j=b_j>0\)，依然取 \(x_j=a_j\)。
- 否则取 \(x_j\ne a_j,x_j\ne b_j\) 即可。
- 否则 \(a_i>b_i=0\)，那么取 \(x_i=a_i\)，那么 \((a,b)\gets(a\oplus x,b)\)。
- 如这一位后手胜，直接取 \(x_j=0\)。
- 剩下的位 \(a_j=b_j>0\)，取 \(x_j\ne 0,x_j\ne a_j\)。
- 如果 \(a_j>b_j=0\)，取 \(x_j=a_j\)。
- 如果 \(b_j>a_j=0\)，取 \(x_j\ne 0,x_j\ne b_j\)。
进一步推广，对于 \(n>2\) 的情形，当且仅当有一个四进制位上恰好只有一种非零数码那么先手必胜，证明类似。
时间复杂度 \(\mathcal O(n\log V)\)。
*5. [ARC163F] Many Increasing Problems
对于每个长度为 \(n\)，值域为 \([1,m]\) 的序列求 CF13C 的答案。
数据范围：\(n,m\le 10^5\)。
考虑那一题的反悔贪心做法：给大根堆中加入两个 \(a_i\) 然后弹出堆顶，答案为 \(\sum a\) 减去最终堆中元素和 \(S\)。
\(\sum a\) 容易求，只要知道每种情况中最终堆里的元素之和。
很自然考虑堆里 \(>k\) 的元素数量，转 01 序列，此时有 \(m-k\) 个 \(1\) 和 \(k\) 个 \(0\)。
每当我们向堆中加入一个 \(1\)，那么 \(S\gets S+1\)，否则 \(S\gets \max(S-1,0)\)。
可以把 \(S\) 的变化看成从 \((0,0)\) 到 \((n,i)\) 的格路，贡献为 \(i\)，但是 \(S=0\) 时不下降是一个很棘手的条件。
我们不妨把令该格路在 \(S=0\) 的时候下降，那么贡献就是 \(i-x\)，其中 \(x\) 表示路径最低点。
不妨重设 \(x\) 为 \(y\) 轴，那么格路变成 \((0,x)\to (n,y)\)，贡献为 \(y\) 且经过 \(y=0\) 不经过 \(y=-1\)。
路径数可以反射容斥，用不经过 \(y=-1\) 的路径数减去不经过 \(y=0\) 的路径数得到：
\[\left(\binom{n}{\dfrac{n+x-y}{2}}-\binom{n}{\dfrac{n+x+y+2}{2}}\right)-\left(\binom {n}{\dfrac{n+x-y}{2}}-\binom {n}{\dfrac{n+x+y}{2}}\right)\\ =\binom{n}{\dfrac{n+x+y}2}-\binom{n}{\dfrac{n+x+y+2}2} \]记 \(i=\dfrac{n+x-y}2\) 表示填入 \(0\) 的数量，由于 \(y\ge x\)，那么要求 \(\dfrac{n-y}2\le i\le n\)。
那么答案就是：
\[\mathrm{Ans}=\sum_{k=0}^{m-1}\sum_i k^i(m-k)^{n-i}\sum_yy\left(\binom{n}{i+y}-\binom{n}{i+y+1}\right)\\ \]设 \(i+y=j\)，则 \(j\ge i,j\ge n-i\)，记 \(j_0=\max(i,n-i)\)那么后面一部分的贡献 \(g_i\) 就是：
\[\begin{aligned} g_i&=\sum_{j\ge j_0} (j-i)\left(\binom{n}{j}-\binom{n}{j+1}\right)\\ &=\sum_{j\ge j_0}\left(j\binom{n}{j}-j\binom{n}{j+1}\right)-i \sum_{j\ge j_0} \left(\binom{n}{j}-\binom{n}{j+1}\right)\\ &=(j_0-i)\binom n{j_0}-\sum_{j>j_0}\binom nj \end{aligned} \]预处理组合数后缀和即可。
现在问题转化为对于每个 \(i\in[0,n)\) 求出：
\[\begin{aligned} f_i &=\sum_{k=0}^{m-1} k^i(m-k)^{n-i}\\ &=\sum_{k=0}^{m-1} (m-k)^n\left(\dfrac{k}{m-k}\right)^i\\ &=\sum_{k=0}^{m-1} (m-k)^n[z^i]\dfrac{1}{1-\dfrac{k}{m-k}z}\\ &=\sum_{k=0}^{m-1} (m-k)^n[z^i]\dfrac{m-k}{m-k-kz} \end{aligned} \]因此：
\[\sum f_iz^i=\sum_{k=0}^{m-1}\dfrac{(m-k)^{n+1}}{m-k-kz} \]可以用分治 NTT 维护通分相加的过程，最后多项式求逆把分母除掉，就能求出 \(f_i\) 的生成函数。
时间复杂度 \(\mathcal O(n\log n+m\log ^2m)\)。
6. [ABC300Ex] Fibonacci: Revisited
给定 \(n,k\)，定义 \(f_n=\sum_{i=1}^k f_{n-i}\)（\(f_1\sim f_k=1\)），求 \(n\) 在二进制下每个子集 \(m\) 的 \(f_m\) 之和。
数据范围：\(k\le 5\times 10^4,n\le 10^{18}\)。
考虑如何计算单项 \(f_n\)，根据 BM 算法，递推矩阵的特征多项式为 \(\Phi(x)=x^k-x^{k-1}-\cdots -1\)，那么 \(f_n\) 就是 \(x^n\bmod \Phi(x)\) 的各项系数之和。
答案就是 \(\sum_{m}x^m\bmod \Phi(x)\)，显然考虑二进制分解 \(n=2^{k_1}+\dots 2^{k_p}\)，那么要求的多项式变成 \(\prod_{i=1}^p(x^{2^k_i}+1)\bmod\Phi(x)\)，可以用类似快速幂的方式维护。
注意到该多项式有良好的性质，我们在计算多项式取模时，消去 \(i\) 次系数 \(f_i\) 等价于给 \(f_{i-1}\sim f_{i-k}\) 加上 \(f_i\)，因此用差分维护可以做到 \(\mathcal O(k)\) 取模。
时间复杂度 \(\mathcal O(k\log k\log n)\)。
7. [ARC164F] Subtree Reversi
给定 \(n\) 个点的树，A 和 B 轮流给点染黑色和白色。
只能染子树全部被染色的点，染色后子树颜色反转（当前点不变）
双方均采取最优策略，求最终有多少黑色棋子。
数据范围：\(n\le 2\times 10^5\)。
显然一个点深度为偶数，那么其颜色与初始相同，否则不同。
因此两个人的目的可以都转成取最少的奇深度点。
讨论几种情况：
- 如果当前有偶深度叶子，两人轮流取一定不影响。
- 否则只有奇深度叶子，这个叶子是其父亲的唯一儿子，那么先手取了这个叶子，后手还能再取一个偶深度叶子，一定很亏，所有两个人轮流取父亲儿子数 \(\ge 2\) 的点。
- 最后每个点都是其父亲的唯一儿子，显然当前人要取离度数 \(\ge 2\) 的祖先最近的一条链，否则只会越亏越多。
每次暴力模拟，复杂度 \(\mathcal O(n^2)\)。
考虑自下而上划分。
注意到两个人的操作可以被描述成一些连续的过程，且每个过程结束后先后手互换。
我们把这些过程对应的树上节点称为簇。
显然每个簇都会在父亲度数 \(\ge 2\) 的奇深度节点处结束。
自下而上维护一些可能簇的子部分，记为组。
显然在奇深度节点处的组操作后先后手互换，在偶深度节点处的组操作后先后手不变。
对于一个奇深度节点，显然选簇的过程未结束，且他的所有儿子当前对应的先后手始终不边，因此新的组由当前点和所有儿子的组组成。
对于一个偶深度节点，由于两个人都会取尽可能小的簇，因此他会在自己儿子中最大的簇被选走后被取，把儿子中最大的组和当前点连起来成新组，剩下的组独立成簇。
最后两人从小到大轮流取簇即可。
时间复杂度 \(\mathcal O(n\log n)\)。
8. [AGC066C] Delete AAB or BAA
给定一个长度为 \(n\) 的字符串 \(S\)，每次删除一个 AAB 或 BAA 子串，问最多删除多少次。
数据范围：\(n\le 10^6\)。
先考虑什么样的子串能被删空。
首先我们要求 A 的数量是 B 的两倍且两端至少有一个 B。
然后尝试证明这个条件是充要的：设 B 数量 \(k\) 个，用 B 分割整个序列，那么有 \(k\) 个空（有一个端点是 B）插 \(2k\) 个 A，那么至少有一段空里 A 数量 \(\ge 2\)。
观察这段空，如果 \(k>1\) 那么这段空至少有一个邻居是 B 且不在端点上（或者原串两端点都是 B），那么这样删掉这个 B 和段内的两个 A 就可以保持这个性质递归。
因此我们可以 dp，\(dp_i=\max\left\{ dp_j+\dfrac{i-j}3\mid S_{(j,i]}\text{ is valid}\right\}\)。
判定是否合法可以把 A 当 \(-1\) B 当 1 求前缀和，用桶维护 \((sum_j,j\bmod 3,S_{j+1})\) 对应的最大 \(dp_{j}-j\) 桶优化即可。
时间复杂度 \(\mathcal O(n)\)。
9. [ABC304G] Max of Medians
给定 \(a_1\sim a_{2n}\)，求一个排列 \((p_1,q_1)\sim (p_n,q_n)\)，最大化 \(\{a_{p_i}\oplus a_{q_i}\}\) 的中位数。
数据范围：\(n\le 10^5\)。
显然先二分，数 \(\ge k\) 的最大对数，然后在 Trie 上解决问题，设当前节点为 \(u\)：
- 如果 \(k\) 的这一位上是 \(0\)：
- 显然先跨越两个子树匹配，设 \(a=\mathrm{siz}(ls_u),b=\mathrm{siz}(rs_u)\)，假设 \(a<b\)。
- 那么左儿子全部被匹配掉，我们只要递归右儿子处理，由于我们要保留 \(a\) 个进行匹配，因此算出来的答案要和 \(\left\lfloor\dfrac{b-a}2\right\rfloor\) 取 \(\min\)，容易构造对应方案（把不在解里面的拿去匹配即可）。
- 否则我们递归 \((ls_u,rs_u)\)，表示两个子树各选一个进行匹配，类似上面的过程分类讨论一下即可。
时间复杂度 \(\mathcal O(n\log^2V)\)。
*10. [ABC305Ex] Shojin
给定 \(n\) 个一次函数 \(f_i=a_ix+b_i\)，定义其权值为 \(\min\{f_{p_1}\circ f_{p_2}\circ\cdots\circ f_{p_n}(0)\mid p_i\}\)。
把该序列划分成 \(k\) 个子段，使得所有段权值之和 \(\le C\)，最小化 \(k\)。
数据范围：\(n\le 2\times 10^5,C\le 10^8,a_i,b_i\ge 1\)。
去掉斜率为 \(1\) 的直线，显然这些人贡献始终是 \(b_i\)，剩余的每个函数都至少让 \(x\) 翻倍，因此所有子段大小 \(\le \log_2C+1\)。
可以证明代价函数满足四边形不等式，那么所有段的最小权值之和关于段数是凸函数。
可以 wqs 二分，对于一个斜率 \(\delta\)，求凸包上这一段的最低点（段数最多的解），此时从最低点每减少一段都会使得代价增加 \(\delta\)，算出最多能增加多少段即可，这样就处理掉了多点共线的情况。
dp 的时候预处理出所有长度 \(\le\log_2C+1\) 的区间，内部代价可以用 Exchange Argument 计算，先操作 \(b_ia_j+b_j<b_ja_i+b_i\) 的 \(i\)，即 \(\dfrac{b_i}{a_i-1}\) 较小的一个即可。
时间复杂度 \(\mathcal O(n\log ^2C)\)。
11. [ABC306Ex] Balance Scale
给 \(x_1\sim x_n\) 和 \((u_1,v_1)\sim (u_m,v_m)\)，求 \(c_i=\mathrm{sgn}(x_{u_i}-x_{v_i})\) 这个序列有多少种可能。
数据访问：\(n\le 17\)。
假如要求 \(c_i\ne 0\)，那么相当于把无向图定向成 DAG，容易发现这就是 Amusement Park。
每次枚举一个 DAG 上极大的无入度的点集 \(S\)，要求其内部是独立集，且容斥系数为 \((-1)^{|S|-1}\)。
那么我们可以 \(g_S=(-1)^{|S|-1}[S\text{ is independent set}]\) 作为容斥系数进行集合幂级数卷积，即：
\[f_S=\sum_{T\subseteq S} g_Tf_{S\setminus T} \]这题中允许加入 \(c_i=0\) 的边，那么我们依然枚举 \(S\)，假如 \(S\) 的导出子图中有边，显然必须用等号缩成一个新的点，设 \(V(S)\) 为导出子图的连通块数，那么容斥系数 \(g_S=(-1)^{V(S)-1}\)。
剩下的问题用子集卷积解决即可。
时间复杂度 \(\mathcal O(2^nn^2)\)。
12. [ARC165E] Random Isolation
给定 \(n\) 个点的树，每次在所有大小 \(>k\) 的连通块中随机选择一个点删除，直到所有连通块大小 \(\le k\)，求期望操作数。
数据范围：\(n\le 100\)。
枚举每个大小 \(>k\) 的连通块 \(S\) 有多少概率出现，显然出现概率之和就是期望操作次数。
设 \(|S|=x\)，\(S\) 的邻域大小为 \(y\)，那么 \(S\) 出现要求 \(y\) 个邻居都出现在 \(S\) 中点之前，概率为 \(\dfrac{x!y!}{(x+y)!}\)。
那么就可以树形 dp，设 \(dp_{u,i,j}\) 表示以 \(u\) 为根满足 \(x=i,y=j\) 的 \(S\) 有多少个。
时间复杂度 \(\mathcal O(n^4)\)。
13. [ARC165F] Make Adjacent
给定 \(a_1\sim a_{2n}\)，其中 \(1\sim n\) 每个出现 \(2\) 次，交换尽可能少的相邻元素使得所有 \(a_{2i}=a_{2i-1}\)，在这个基础上求出字典序最小的 \(\{a_i\}\)。
数据范围：\(n\le 2\times 10^5\)。
考虑 \(n=2\) 的情况，那么本质不同的初始序列只可能是 \(0011,0101,0110\)，其中前两种都必须变成 \(0011\)，第三种可以变成 \(0011/1100\)。
类似推广，\(a_{l_i}=a_{r_i}=i(l_i<r_i)\)，那么最终排列 \(i\) 必须在 \(j\) 前面当且仅当 \(l_i<l_j,r_i<r_j\)。
那么我们可以 CDQ 分治优化建图，原问题变成求最小拓扑序（带虚点）。
那么把 \(1\sim n\) 用优先队列维护，每次取出最小的点，对于其他虚点用一个普通队列维护，每次优先处理虚点即可。
时间复杂度 \(\mathcal O(n\log n)\)。
14. [ABC308Ex] Make Q
定义一个 Q 子图是一个环（长度 \(\ge 3\)）加上一条从连接环上和环外点的边的图。
给定一张 \(n\) 个点 \(m\) 条边的带权无向图，求其最小权 Q 子图。
数据范围：\(n\le 300,m\le n^2\)。
考虑枚举环外边 \(u\to v\) 并删掉，然后变成求过 \(u\) 的最小环，这就是旅行者那题的弱化版，Dijkstra 求出最短路，然后记录每个点最短路上的第一条边，取所有两端染色不同的边更新答案即可。
朴素实现 Dijkstra 是 \(\mathcal O(n^2)\) 的。
但我们要枚举 \(n^2\) 条边，换一个视角，先钦定一个过 \(u\) 的环，那么环外边显然是剩余边中权值最小的一条，算上环上被删去的两条，这条边一定是 \(u\) 的所有出边中权值前三小的边中的一条。
那么每个点只要枚举删掉三条边即可。
时间复杂度 \(\mathcal O(n^3)\)。
*15. [ABC309Ex] Simple Path Counting Problem
题目大意
\(n\) 次操作令 \(x\gets x+1/x-1/x\)，值域不能超过 \([1,m]\)，求从 \(A\) 中某个数变成 \(B\) 中某个数的方案数。
数据范围：\(n\le 10^9,m\le 10^5\)。
朴素想法就是令 \(F(z)=(z+z^{-1}+1)^n\)，但是这样无法处理值域在 \([1,m]\) 之间的限制。
考虑构造 \(f_0,f_{m+1}\) 两个空位置用来销毁越界的项的贡献。
但是这两个项在转移的时候也会向 \(f_1,f_m\) 转移，因此我们想让他们时刻为 \(0\)。
我们可以构造 \(f_{m+2}\sim f_{2m+1}\)，其中 \(f_{2m+2-x}=-f_x\)，即对称 \(f\) 并取反。
那么 \(f_{m+1}\) 每次会被 \(f_{m}\) 和 \(f_{m+2}=-f_m\) 转移，而 \(f_0\) 在 \(\bmod z^{2m+2}\) 意义下会被 \(f_1\) 和 \(f_{2m+1}=-f_1\) 转移，显然这两个项始终为 \(0\)。
那么最后一行每个点答案的生成函数就是 \(\sum a_iz^i\times (z+1+z^{2m+1})\bmod z^{2m+2}\)。
多项式快速幂解决。
时间复杂度 \(\mathcal O(m\log m\log n)\)。
*16. [ABC310Ex] Negative Cost
有 \(n\) 个操作，每个可以消耗 \(c_i\) 费用打出 \(d_i\) 伤害，任何时候费用不能为负数，求最少操作次数使得伤害 \(\ge m\)。
数据范围：\(n,|c_i|\le 300,m\le 10^{18}\)。
把 \(c_i\) 取反表示费用增量，记 \(V=300\) 表值域。
首先我们可以把一个操作序列等效成若干序列（长度之和和造成伤害之和相同），且每个序列的最大前缀和 \(\le 2V\)，证明如下：
设当前的序列和为 \(S\)，考虑如下过程：
- 若 \(S\le V\)，任选一个 \(c\ge 0\) 插入末尾，那么 \(S'=S+c\le 2V\)。
- 如果当前 \(S>V\)，任选一个 \(c<0\) 插入末尾，那么依然有 \(S'>0\)。
显然如果某个时刻没有 \(c\ge 0\) 的元素了，那么直接把剩下的 \(c<0\) 全部插进去也不会使得总和 \(<0\)。
否则如果某个时刻没有 \(c<0\) 的元素了，剩余的 \(c\ge 0\) 每个独立形成一个序列即可。
对于一个前缀和 \(\le 2V\) 的合法序列，我们可以等效成若干个长度 \(\le 2V\) 的序列，证明如下：
否则对于长度 \(>2V\) 的序列，根据抽屉原理一定能取两个位置使得 \(s_x=s_y\)。
我们把 \(s_{(x,y]}\) 单独取出来，这一段 \(c\) 之和为 \(0\)，先重排成一个合法序列，然后根据上一个引理，再等效成前缀和 \(\le 2V\) 的若干合法序列即可。
不断分割直到所有序列长度 \(\le 2V\)。
因此我们只要考虑若干长度 \(\le 2V\) 且最大前缀和 \(\le 2V\) 的合法序列，并把它们拼起来即可。
定义长度为 \(i\) 的这样的序列的最大伤害值为 \(f_i\)，那么最优解一定由若干 \(f_1\sim f_{2V}\) 拼成，求出这些 \(f_i\) 的复杂度为 \(\mathcal O(nV^2)\)。
直觉上我们会取很多 \(\dfrac{f_i}i\) 最大的序列，设其为 \(f_x\)。
可以证明其他的序列最多取 \(2V\) 个：
把这些序列拼起来，定义 \(q_i\) 为前 \(i\) 个序列的长度之和。
如果有 \(>2V\) 个序列，那么根据抽屉原理一定有两个 \(q_i\equiv q_j\pmod x\)。
那么这若干个序列合起来一定不如用 \(\dfrac{q_j-q_i}x\) 个 \(f_x\)。
所以我们再 dp 求出长度总和为 \(i\) 的若干个序列的最优解 \(g_i\)，这个的范围为 \(4V^2\)，背包复杂度 \(\mathcal O(V^3)\)。
时间复杂度 \(\mathcal O(nV^2+V^3)\)。
17. [ARC166E] Fizz Buzz Difference
\(T\) 次询问 \(n,a,b\)，求 \(L,R\) 使得 \([L,R]\) 中 \(a\) 的倍数比 \(b\) 的倍数恰好多 \(n\) 个，最大化 \(R-L\) 的基础上最小化 \(L\)。
数据范围：\(T\le 2\times 10^5,n,a,b\le 10^6\)。
很显然把可以把原限制改成 \(n_a-n_b\le n\)。
那么很自然的贪心想法就是取 \(L\bmod a=1,R\bmod a=-1\)，那么 \(L=ua+1,R=va-1\)。
那么 \(n_a-n_b=(v-u-1)-\left(\left\lfloor\dfrac{va-1}b\right\rfloor-\left\lfloor\dfrac{ua}b\right\rfloor\right)\)，枚举 \(k=v-u\)，那么我们肯定想令后一部分尽可能大。
设 \(r=ua\bmod b\)，后一部分等于 \(\dfrac{va-1-(r+ka-1)\bmod b}b-\dfrac{ua-r}b=\dfrac{ka-1+(r-(r+ka-1)\bmod b)}{b}\)。
那么 \(r-(r+ka-1)\bmod b\) 在 \(r<b-(ka-1)\bmod b\) 时是 \(-(ka-1)\bmod b\)，否则是 \(b-(ka-1)\bmod b\)。
我们显然要让 \(r\ge b-(ka-1)\bmod b\)，但是注意 \(r=ua\bmod b\)，因此 \(r\) 最大值是 \(b-\gcd(a,b)\)。
此时原式取得 \(n_a-n_b=k-\left\lfloor\dfrac{ka-1}b\right\rfloor-[\gcd(a,b)\le (ka-1)\bmod b]\)。
显然这个式子具有单调性，可以直接二分。
求出 \(k\) 之后，如果 \(\gcd(a,b)>(ka-1)\bmod b\) 那么直接取 \(u=0\) 即可，否则我们要求最小的 \(u\) 使得 \(ua\bmod b\ge b-(ka-1)\bmod b\)。
那么我们可以看成这样一个问题，求 \(L\le xa\bmod p\le R\) 的最小自然数解：
首先如果 \(l=0\) 直接解决。
其次如果 \([l,r]\) 中有 \(a\) 倍数，即 \(a\left\lceil \dfrac la\right\rceil\le r\) 那么 \(x_{\min}=\left\lceil \dfrac la\right\rceil\)。
否则设 \(k=\left\lfloor\dfrac{xa}p\right\rfloor\)，我们只需最小化 \(k\)，此时 \(x\ge \left\lfloor\dfrac{kp+l}a\right\rfloor\)。
那么 \(l\le ax-kp\le r\) 可以推出\(ax-r\le kp\le ax-l\)，进一步得到 \((-r)\bmod a\le kp\bmod a\le (-l)\bmod a\)，可以递归处理。
注意到每次递归都会使得 \((a,p)\gets (p\bmod a,a)\)，因此复杂度同辗转相除法。
时间复杂度 \(\mathcal O(T\log V)\)。
18. [ARC176D] Swap Permutation
给定 \(n\) 阶排列 \(p_1\sim p_n\)，\(m\) 次操作选择 \(1\le i<j\le n\) 并交换 \(p_i,p_j\)。
求最终每个排列的 \(\sum_{i=1}^{n-1}|p_i-p_{i+1}|\) 之和。
数据范围：\(n,m\le 2\times 10^5\)。
考虑如何刻画最终一个排列的权值，考虑 01 序列，设 \(q_{x,i}=[p_i>x]\)，那么最终一个排列的权值就是 \(\sum_{x,i}[q_{x,i}\ne q_{x,i+1}]\)，这是显然的因为这样的 \(x\) 恰有 \(|p_i-p_{i+1}|\) 个。
那么我们对于每个 01 序列，选定 \(q_{i},q_{i+1}\) 观察 \(m\) 次交换后有多少种方案使得其变成 \((0,1)\)。
考虑 dp，那么状态为 \(f_{i,s}\)，其中 \(i\) 是操作次数，\(s\) 是当前状态，只有 \((0,0),(1,1)\) 和 \((0,1)/(1,0)\) 三种，转移也是简单的。
那么我们可以用 \(3\times 3\) 矩阵加速转移，快速算出每种 \((q_i,q_{i+1})\) 对答案的贡献，至于每种 \(q_i\) 有多少对可以简单统计。
时间复杂度 \(\mathcal O(n\log m)\)。
19. [ABC313F] Flip Machines
给定 \(n\) 个卡片，正面 \(a_i\) 反面 \(b_i\)，第 \(i\) 个操作以平均的概率反转 \(u_i/v_i\)，操作 \(1\sim m\) 个中的若干个使得最终所有向上卡面的数之和期望最大。
数据范围：\(n\le 40,m\le 10^5\)。
注意到每个被操作至少一次的卡最终期望总是 \(\dfrac{a_i+b_i}2\)。
特判 \(u_i=v_i\) 的情况，如果 \(a_i<b_i\) 加入集合 \(S\)，否则加入 \(T\)。
显然一个操作两端都在 \(S\) 必操作，都在 \(T\) 必不操作。
剩下的操作看成连接 \(S,T\) 的边，然后讨论 \(|S|\) 和 \(|T|\) 大小关系：
- 如果 \(|S|>|T|\)，那么枚举 \(|T|\) 中哪些数被操作了，那么所有与这些数相连的 \(|S|\) 中的元素必被选，直接求和。
- 否则可以 dp，\(f_{i,S}\) 表示 \(T_1\sim T_i\) 选若干个使得邻域覆盖 \(S\) 的最小代价，转移很简单。
时间复杂度 \(\mathcal O(n2^{n/2})\)。
20. [ABC313Ex] Group Photo
给定 \(a_1\sim a_n,b_1\sim b_{n+1}\)，重排 \(a,b\) 使得 \(b_i> \min(a_i,a_{i-1})\)，求有多少可能的 \(\{a_i\}\)。
数据范围：\(n\le 5000\)。
设 \(c_i=\min(a_i,a_{i-1})\)。
相当于从大到小排列 \(c_i,b_i\) 使得对应位 \(b>c\)。
从大到小插入 \(a_i\)，每次插入时考虑左右邻居有几个被钦定，那么产生新的 \(c\) 就是 \(a_i\)。
\(f_{i,j}\) 表示插入了最大的 \(i\) 个，其中有 \(j\) 对邻居被锁定变成 \(c\)，降序排列 \(b_i\) 即可 check。
降序排列 \(b_i\)，那么转移就是 \(f_{i+1,j+k}=f_{i,j}(i+1-j)[b_{j+k}>a_j](1+[k=1])\)。
其中 \(k\) 表示新增多少 \(c\)，\(k=1\) 可以选择哪边变成 \(c\)。
时间复杂度：\(\mathcal O(n^2)\)。
标签：Atcoder,le,题目,dfrac,复杂度,那么,选做,Link,mathcal From： https://www.cnblogs.com/DaiRuiChen007/p/18203843