ARC C~F 随机做题

一些符号：$\color{blue}\Diamond$ 表示从中很有收获的题，$\color{blue}\Box$ 表示差不多会，参考题解做出来的题，$\color{blue}\triangle$ 表示完全不会，看题解才会的题，$\color{blue}\nabla$ 表示之前改的题。在题解中穿插表示具体部分。

[ARC104C] Fair Elevator (*2009)

考虑有一个区间 $[l_i,r_i]$，钦定没有另一个区间 $[l_j,r_j]$ 满足 $l_j<l_i\wedge r_j>r_i$。考虑 $l_i+1$ 位置对应的右端点，一定为 $r_i+1$。于是确定了 $[l_i,r_i]$ 就可以确定 $[l_i+1,r_i+1]\cdots [r_i-1,r_i-1+r_i-l_i]$。

然后可以 dp。设 $dp_i$ 为 $[1,i]$ 内是否都满足。转移是枚举一个 $j>i$，$[i,j]$ 配对，然后暴力 $O(n)$ 判断是否合法。细节多。时间复杂度 $O(n^3)$。

[ARC104D] Multiset Mean $\color{blue}\Box$ (*2251)

朴素 dp 是设 $dp_{i,j,k}$ 表示当前选完了 $[1,i]$ 内的数，选了 $j$ 个，和为 $k$ 的方案数。每次枚举选了几个 $i$，复杂度为 $O(n^7)$。

套路地，考虑先钦定一个 $avg=k$，于是可以省去 $j$ 这一维，变成 $O(n^6)$。

然后发现其实有很多重复算的东西。考虑钦定了 $avg$ 之后，把 $[1,n]$ 变成了 $[-avg+1,-1],0,[1,n-avg]$。$0$ 不用管，乘上随意选 $[0,k]$ 个的 $k+1$ 种方案即可。然后要求 $[-avg+1,-1]$ 和 $[1,n-avg]$ 这两部分取得的数和为 $0$，$\color{blue}\Box$也就是求 $[1,avg-1]$ 和 $[1,n-avg]$ 中选出和相同的方案数。

于是设 $dp_{i,j}$ 为已经选完了 $[1,i]$，和为 $j$ 的方案数。暴力转移是 $O(n^5)$ 的，加上前缀和优化多重背包之后 $O(n^4)$ 可过。$\color{blue}\Diamond\Box$这个前缀和的方法是，设 $f_j=dp_{i,j}+f_{j-i}$ 然后做。

[ARC104E] Random LIS $\color{blue}\Diamond$ (*2824)

首先期望转 LIS 长度和除以方案数。LIS 这个东西不好刻画，但是发现 $n=6$ ，所以考虑直接枚举每个数排名，也就是枚举 $X_i$ 离散化后的序列。

然后考虑知道这个序列之后怎么求方案数。先想一个弱化版的问题：有 $m$ 个数，已知他们的排名，每个数的取值范围为 $[1,k]$，$k$ 为定值。求方案数。答案显然是 $\binom{k}{m}$。

回到原问题，尝试转化成弱化版问题。注意到值域非常大（$V=10^9$）但是 $n=6$ 非常小。$\color{blue}\Diamond$这启示我们，$\color{blue}\Diamond$ 要不只有小部分值是有用的，要不可以把一段值放在一起算。这题显然是后者。

考虑把序列 $A$ 排序后去重得到序列 $B$，于是发现对于 $(B_{j-1},B_j]$ 这个区间，能取到区间内任意一个数的 $X_i$ 的集合相同。也就是说，我们如果知道了对于每个 $(B_{i-1},B_i]$，哪些 $X_i$ 在这个区间中，就可以用弱化版的方法算出每个 $i$ 的方案数，最后再乘起来即可。

这里再次暴力枚举每个排名所对应的数属于哪个 $(B_{i-1},B_i]$ 的 区间即可。时间复杂度远小于 $O(n^{2n})$。

[ARC104F] Visibility Sequence $\color{blue}\Diamond\Box$ (*3213)

$\color{blue}\Diamond$ 对于序列上和某些位置的最小值最大值计数相关的，考虑一些类似笛卡尔树的 dp，更进一步，按照最大值/最小值划分区间后进行区间 dp。设 $dp_{i,j,k}$ 表示 $[i,j]$ 这个区间内，所有值 $\le k$ 的方案数。从类似 $dp_{i,l-1,k}\times dp_{l+1,j,k-1}$ 转移过来。

此时有一个问题：为什么这样不会算重/漏？首先不会算漏，因为每一步都贪心地取到了最大范围，能算的情况都会算到。并且不会算重，$\color{blue}\Diamond$ 感性理解，因为从最终状态开始往下推，如果有一个 $j$ 可行，不会从 $j-1$ 转移过来。于是每一种 $p$ 都对应了唯一一种转移过程。

但是发现 $V\le 10^5$，不过这是诈骗，$\color{blue}\Diamond\Box$ 因为发现我们只关心取值大小可能导致的大小关系，所以 $a_i$ 可以向 $n$ 取 $\min$，只用这部分就可以凑出来需要的大小关系。时间复杂度 $O(n^4)$。

[ARC105C] Camels and Bridge (*1964)

$n=8$ 于是直接枚举排列（最近怎么做了 3 道）。考虑如果有两个限制 $i,j$ 满足 $l_i\ge l_j,v_i\le v_j$ 则限制 $j$ 是没用的，丢掉。然后形成了 $l_i,v_i$ 都单调上升的序列。

考虑从前往后依次枚举，确定第 $i$ 只骆驼的位置时，枚举所有 $j<i$，考虑区间内的体重总和，再二分出限制，确定可以放的最左的位置即可。贪心地想，每一个都尽可能往左靠是正确的。时间复杂度 $O(n!n^2\log m)$。

[ARC105D] Let's Play Nim (*1871)

其实就是问能不能把每个数分配到一个集合中使得每个集合中数字和的异或和为 $0$。

考虑构造。如果 $n$ 为偶数，先手每次选最大的，丢到一起，记选择的序列为 $A$，后手选的为 $B$，则 $\sum A_i\ge\sum B_i$，又 $x\oplus y\le x+y$，则不管后手怎么选，他选的那一部分 $\oplus$ 和都 $\le\sum A_i$，取等当且仅当 $a$ 中的数可以两两配对，每对内相等。能取等后手胜，否则先手。

如果 $n$ 为奇数，则类似的，先手不管选什么数，后手每次选当前最大加入先手第一次放的那一堆，则一定有这一堆的和大于其它的所有数之和。所以后手必胜。

[ARC105E] Keep Graph Disconnected (*2615)

考虑如果没有第一个条件，则一共有 $\binom{n}{2}-m$ 条边可以加，看这个数的奇偶性即可。

有了第一个条件，注意到最后一定剩下两个集合，$1$ 号点在其中一个，$n$ 在另一个。设两个集合分别为 $S,T$，则根据 $|S|\times|T|$ 的奇偶性即可得出真实胜负。接下来就看双方如何操作可以使得最后奇偶性变成怎么样。

最详细的一集：

if((n&1)){//总点数为奇数 -> 最后一定剩 01 -> 胜负情况不变
	if(p&1){
		puts("First");
	}else{
		puts("Second");
	}
	return;
}
if(x+y==2){//无法操作 -> 直接算影响
	p-=x==2;
	if(p&1){
		puts("First");
	}else{
		puts("Second");
	}
	return;
}
if(p&1){//原本状态先手必胜
	if((x+y)&1){//可以操作奇数次 -> 最后操作的人是先手 -> 先手希望最后不为 101
		if(!u||!v){//一开始 1,n 中有一个 0 -> 先手可以控制最后 1,n 一定有一个 0 -> 先手胜
			puts("First");
		}else if(!y){//一开始全 1，先手先使 1 或 n 变 0 -> 后手只能把这个变为 1 否则成上面情况 -> 可以保持后手操作完后全 1 -> 先手胜
			puts("First");
		}else{//一开始有 0，后手可以保持操作完后中间有 0，1,n 为 1 -> 后手胜
			puts("Second");
		}
	}else{//可以操作偶数次 -> 最后操作的是后手 -> 后手希望最后不为 000
		if(!u||!v){//一开始 1,n 中有一个 0 -> 先手可以保持操作完后最后 1,n 一定都是 0 -> 先手胜
			puts("First");
		}else{//一开始全 1,n 都为 1，后手可以保持操作完后 1,n 都为 1 -> 后手胜
			puts("Second");
		}
	}
}else{//原本状态后手必胜
	if((x+y)&1){//可以操作奇数次 -> 最后操作的是先手 -> 先手希望最后不为 000
		if(!u&&!v){//一开始 1,n 都为 0，后手可以保持操作完后 1,n 都为 0 -> 后手必胜
			puts("Second");
		}else{//一开始 1,n 中有一个 1，先手可以保持操作完后 1,n 都是 1 -> 先手必胜
			puts("First");
		}
	}else{//可以操作偶数次 -> 最后操作的是后手 -> 后手希望最后不为 101 
		if(!u&&!v){//一开始 1,n 都为 0，后手可以保持操作完后 1,n 都为 0 -> 后手必胜
			puts("Second");
		}else if(!u||!v){//一开始 1,n 有一个 1，先手把其中 0 变 1
			if(y==1){//中间没有 0，后手把 1,n 之一变成 0，保持操作完后中间一直全 1 -> 后手必胜
				puts("Second");
			}else{//中间有 0，先手保持操作完后 1,n 为 1，中间有 0 -> 先手必胜
				puts("First");
			}
		}else{//一开始 1,n 都为 1，先手保持操作完后 1,n 为 1，中间有 0 -> 先手必胜
			puts("First");
		}
	}
}

[ARC105F] Lights Out on Connected Graph $\color{blue}\Diamond\Box$ (*3231)

二分图，想到黑白染色。于是对于一个点集 $S$，枚举其染为白的子集 $T$，则 不要求连通，$S$ 的染色方案数就是 $f_S=\sum\limits_{T\subseteq S}2^{cnt_S-cnt_T-cnt_{S\setminus T}}$。其中 $cnt_S$ 表示 $S$ 的导出子图的边数。

但是这是不一定联通的情况。考虑如果不限制是二分图，求连通的方案数。这个弱化问题也很难直接做，$\color{blue}\Diamond$ 于是考虑容斥。对于本题，设 $dp_S$ 为 $S$ 是一个连通块，染色的方案数。转移就是减去不为一个连通块的方案数，即 $dp_S=f_S-\sum\limits_{T\subseteq S}dp_Tf_{S\setminus T}$。注意到这样还会算重，于是钦定 $\operatorname{lowbit}(S)=\operatorname{lowbit}(T)$ 就可以了。

在做这题时的主要问题还是太过纠结边的连法。$\color{blue}\Diamond\Box$ 其实二分图的性质很好，只要对染色方式计数就行了。

[ARC106C] Solutions (*1225)

最简单的一集。发现 A 做法能取到最大值，所以 $m<0$ 无解。$m=0$ 用脚构造。$n-m\le 1$ 显然无解，其他用脚构造即可。

[ARC106D] Powers (*1988)

先转换成 $\sum\limits_{l=1}^{n-1}\sum\limits_{r=l+1}^{n}(a_l+a_r)^k=\sum\limits_{l=1}^n\sum\limits_{r=1}^n(a_l+a_r)^k-2^k\sum\limits_{i=1}^na_i^k$

$\sum\limits_{l=1}^{n}\sum\limits_{r=1}^{n}(a_l+a_r)^k$

$=\sum\limits_{l=1}^{n}\sum\limits_{r=1}^{n} \sum\limits_{i=0}^ka_l^ia_r^{k-i}\binom{k}{i}$

$=\sum\limits_{i=0}^k\binom{k}{i}\sum\limits_{l=1}^{n}a_l^i\sum\limits_{r=1}^{n}a_r^{k-i}$

令 $S(x)=\sum\limits_{i=1}^na_i^x$，则

$ans_k=\sum\limits_{i=0}^k\binom{k}{i}S(i)S(k-i)$。

这几个都可以简单预处理，于是做完了。时间复杂度 $O((n+k)k)$。

[ARC106E] Medals $\color{blue}\Diamond$ (*2825)

分配某奖牌，$\color{blue}\Diamond$ 考虑转化成匹配，即每个人要找到 $k$ 个可行位置和它匹配。$\color{blue}\Diamond$ 匹配的可行性问题，想到 Hall 定理，而且数据范围也支持我们枚举集合。

于是二分答案 $ans$，注意到 $nk\le ans\le 4nk$，于是暴力枚举每一天有哪些人在，高维前缀和算出和人的集合 $S$ 有交的位置个数 $f_S$，看是否有 $\forall S,f_S\ge k|S|$ 即可。时间复杂度 $O(2^nn\log nk)$。

[ARC106F] Figures $\color{blue}\Diamond$ (*2755)

第一次用 GF 推式子。

翻译一下就是这颗树每个点的度数 $m\le a_u$，并且要额外乘上 $a_u^{\underline m}$ 的权值，求所有树的权值之和。

由于是 $deg_u$ 的限制，所以考虑 prufer 序列。考虑枚举每个点的度数为 $deg_u$，变成 prufer 序列，则有 $ans=(n-2)!\sum\limits_{\sum deg_i=n\times2-2}\prod\limits_i\frac{a_i^{\underline{dep_i}}}{(deg_i-1)!}=(n-2)!\sum\limits_{\sum deg_i=n\times2-2}\prod\limits_i\binom{a_i}{deg_i}deg_i$。可以背包 dp $O(n^2)$ 解决。

但是 $O(n^2)$ 显然不够，不过背包很难优化。$\color{blue}\Diamond$ 此时想到 GF（但是我一道 GF 都没做过是怎么想到的？？？）。设 $F_i(x)$ 为第 $i$ 个点对应的 GF，则有：

$F_i(x)=\sum_{j}\binom{a_i}{j}jx^j$

$=\sum_j\frac{a_i!}{(a_i-j)!j!}jx^j$

$=\sum_j\frac{a_i!}{(a_i-j)!(j-1)!}x^j$

$=a_i\sum_j\frac{(a_i-1)!}{(a_i-j)!(j-1)!}x^j$

$=a_i\sum_j\binom{a_i-1}{j-1}x^j$

注意到此时 $j-1$ 比较不好看，于是我们默认给每个点分配一个度数（事实上这也是必须要的），则限制变成 $\sum deg_i=n-2$，上式变成 $a_i\sum_j\binom{a_i-1}{j}x^j$。

要求的即为 $[x^{n-2}]\prod_iF_i(x)$。

将 $F_i(x)$ 转为封闭形式即为 $F_i(x)=m(1+x)^{m-1}$。

则 $\prod_iF_i(x)=(\prod a_i)(1+x)^{\sum a_i-n}$。

再转回形式幂级数为 $\prod_iF_i(x)=(\prod a_i)\sum\limits_{j}\binom{\sum a_i-n}{j}$。

则 $ans=(n-2)!(\prod a_i)\binom{\sum a_i-n}{n-2}$。$O(n)$ 解决。

[ARC107C] Shuffle Permutation (*1223)

又是简单的一集。首先行列是相互独立的，如果第 $i$ 行和第 $j$ 行可以互换则连一条边，容易发现这样在同一个连通块内的行之间顺序任意，方案数为阶乘。全部乘起来就是答案。

[ARC107D] Number of Multisets $\color{Blue}\Box\Diamond$ (*2099)

考虑将操作放到二叉树森林中。限制就是二叉树一共有 $k$ 个根，$n$ 个叶子，并且没有只有一个儿子的节点。合法的二叉树和可重集形成双射。

$\color{Blue}\Box\Diamond$ 自底往上考虑每一层，类似阶梯型 dp，于是就有两种操作：在这一层新增一个点，或者在上面新增一层。第二种操作要求当前层有偶数个节点，随后每两个相邻节点都会并到一个父亲下面。

再考虑两种操作对原问题的影响：第一种显然是使元素数 $+1$，和 $+1$。第二种会使全部元素对和的贡献 $\times\frac{1}{2}$，也就是使和 $\times\frac{1}{2}$，并要求和此时为偶数。

于是设 $dp_{i,j}$ 表示前 $i$ 个数，和为 $j$ 的方案数。则有 $dp_{i,j}=dp_{i-1,j-1}+dp_{i,j\times 2}$。$O(n^2)$ 解决。

[ARC107E] Mex Mat $\color{blue}\nabla$ (*2604)

发现多操作几轮就一定有 $a_{i,j}=a_{i+1,j+1}$。于是暴力做个 $10$ 轮后算对角线即可。证明不想写了。

[ARC107F] Sum of Abs $\color{blue}\nabla\Diamond$ (*3130)

首先考虑，最优情况下，所有 $B_i<0$ 的和 $B_i\ge 0$ 的之间不连通，答案为 $\sum|b_i|$。

但是显然很多时候取不到这个上界，$\color{blue}\Diamond$ 但是这启示我们将最后选择贡献 $-B_i$ 的和 $B_i$ 的分开，两者之间不能有连边。这相当于分成两个集合，一个是贡献 $B_i$ 的，一个是 $-B_i$ 的。$\color{blue}\Diamond$ 于是考虑最小割建模。

考虑先令 $B_i\ge 0$ 的贡献 $B_i$，否则贡献 $-B_i$。如果 $i$ 不在原来所属的集合，则会造成 $-2|B_i|$ 的贡献。如果删掉 $i$ 点，则会造成 $-(A_i+|B_i|)$ 的贡献。如果 $i,j$ 间有边且不在一个集合，则造成 $-\inf$ 的贡献。这样连边即可。

[ARC108C] Keep Graph Connected (*1460)

感觉是更简单的一集。显然拎出来一棵生成树再随便染色就做完了。

[ARC108D] AB (*1987)

考虑推一些性质。一开始序列是 AB，不妨设 $c_{AB}=A$，另一种情况大概是对称的。则序列会变成 AAB。此时发现，右半边仍然是 AB，怎么做都只能再增加一个 A。所以只用考虑左半边的 AA。

同时注意到这要求最终的 $s_{n-1}=A$。

• 如果 $c_{AA}=A$，那么最终序列就只有 AAA...AB 这一种情况。
• • 否则，若 $c_{BA}=B$，则可以发现，任何一个 $s_1=A,s_{n-1}=A,s_n=B$ 的序列都可以构造出来，方法是先不管开头的 A 和结尾的 B ，每次找到最后一个连续段，先把这个连续段的第一个位置填上，再往后填。故方案数为 $2^{n-3}$。
  • 否则还是类似上面的，但是此时不能有两个连续的 B，因为 $c_{AB}=c_{BA}=A$。这是一个经典计数问题，设 $f_n$ 为长为 $n$ 的序列的方案数，则 $f$ 为 $f_0=1,f_1=2$ 的斐波那契数列。方案数为 $f_{n-3}$。

$c_{AB}=B$ 的答案是类似的，对称地推一下即可。

[ARC108E] Random IS $\color{blue}\Diamond$ (*3101)

一个很重要的性质：如果已经确定 $l,r$ 被选中，那么 $(l,r)$ 内的期望就和其他位置无关了。于是想到进行一个区间 dp：设 $dp_{i,j}$ 表示已经确定 $i,j$ 选中，$[i,j]$ 区间内的期望长度。转移就是枚举一个 $k$ 表示 $[i,j]$ 内下一个选的是 $k$，算所有合法的 $dp_{i,k}$ 和 $dp_{k,j}$ 之和再除以可能数量。

做的时候有一个问题：为什么这样会把先选 $l,r$ 再选一个 $k>r$ 的情况算上。$\color{blue}\Diamond$ 事实上此时没有必要关注选数的顺序，只要关注选了什么就行了。于是这样是正确的。

然后发现可以 BIT 简单维护，时间复杂度 $O(n^2\log n)$ 解决。

[ARC108F] Paint Tree (*2646)

这题之前自己做出来了，两次/hanx

首先有关键性质：若最大距离的同色点对为 $u,v$，树上的任意一条直径 $(s,t)$ 满足 $s=u,s=v,t=u,t=v$ 其中至少一个成立。

证明：反证。若有一条直径两端点为 $s,t$ 且 $u,v$ 不是任何的一个 $s$ 或 $t$，$s,t,u,v$ 互不相同，钦定 $dis(s,u)<dis(t,u)$，则 $col_u\not=col_t$。同时，因为 $(s,t)$ 为直径，$dis(u,t)<dis(s,t)$，$dis(u,v)<dis(s,v)$，于是 $col_s\not=col_v$，又 $col_u=col_v$，则 $col_s=col_t$，此时显然 $s,t$ 同色且距离更远，不成立。

所以先找出任意一条直径 $(s,t)$，有 $2^{n-1}$ 种情况同色，答案为 $dis(s,t)$。否则，钦定 $col_s=0$，对于每个点 $u$ 考虑钦定 $col_u=0/1$ 的时，有多少种情况使得 $u$ 与一个直径端点的距离是最终答案。

预处理出 $\max(dis(u,s),dis(u,t))$ 然后排序后，处理出此时选这个点做答案的其中一个端点是否可行（$\max(dis(u,s),dis(u,t))\ge\max_{v\not=u}\min(dis(v,s),dis(v,t))$）有多少点 $v$ 是 $col_v$ 为 $0/1$ 都行（即为排序后排名 $-1$），然后计算即可。最后将这部分贡献 $\times 2$，因为加上 $col_s=1$ 的情况。

[ARC109C] Large RPS Tournament (*1167)

考虑这个过程是一棵完全二叉树。你对 $s+s$ 暴力做就得到了更上一层循环的字符串。这样做 $m$ 遍就行了。

[ARC109D] く $\color{blue}\triangle$ (*2394)

这种题怎么做？完全不会。

[ARC109E] 1D Reversi Builder $\color{blue}\Diamond$ (*2661)

因为表面是一个博弈，所以先考虑分析两方的最优策略。考虑分析一些性质。

Lemma：黑白棋子构成级极长同色连续段数量不会超过 $2$。

证明显然，如果在某个时刻从 $2$ 变成了 $3$，那么一定会将一段覆盖，变成 $2$ 个极长同色连续段。

然后，对于这种覆盖的问题，一般都是有很多位置没有用，只用考虑一些特殊的位置。对于这题，由于是两个相同位置覆盖中间的，所以尝试着只考虑每种颜色最左/右出现的位置。

容易发现，令 $c_i$ 为列表上位置 $i$ 的颜色，若 $c_1=c_n$，那么最后全部一定都是 $c_1$ 的棋子。证明显然。

否则不妨钦定 $c_1=0,c_n=1$。此时我们只用关注最后一个 $0$ 的位置 $x$ 和最后一个 $1$ 的位置 $y$。若 $x<y$ 则 $x+1=y$，答案为 $n-x+1$。否则手玩发现，若先取到 $x$ 再取到 $y$，那么黑方在取到 $x$ 后可以直接取 $x+1$，因为 $[x+1,n]$ 全黑，所以 $x+1$ 不会再变成白色。同时 $y$ 还没取，取到 $y$ 后 $[y,n]$ 全黑，也无法变成白色。所以最后黑棋数量为 $n-y+1$。

那么策略就很显然了：黑方尽可能往 $x$ 处靠，白方往 $y$。直接对这个计数也是简单的：枚举起点 $s$，分成 $y<s<x,s\le y<x,y<x\le s$ 以及一些特殊情况，分别预处理一些东西然后算。作者也是这么过的。

但是你会发现这太蠢了！除了 $y<s<x$ 之外，的所有情况，$\color{blue}\Diamond$ 如果将所有黑白翻转，答案就会变成 $n-ans$。若 $y<s<x$ 且 $x-s\not=s-y$ 也满足这个性质。此时期望就是 $\frac{n}{2}$。但是若 $x-s=s-y$，黑方由于先手，所以一定能抢先取到 $x$。于是期望要加上 $\frac{2^{x-y-1}(x-y+1)}{2^n}$。只用简单预处理，统计所有这样的贡献之和即可。

[ARC109F] 1D Kingdom Builder $\color{blue}\triangle\Diamond$ (*3625)

一个非常 educational 的想法：$\color{blue}\Diamond$ 不从怎么进行操作入手，而是从最终形态入手，再根据可能的最后的形态推出最小操作次数。

考虑最后会形成若干连续段。对于每个连续段，都是先标记其中的一部分，最后再拓展成完整的连续段。

然后对第一步讨论。若填的第一个位置两边颜色不同，则一定要不断扩张直到两边相同，不妨为 $0$。

然后 $1$ 没有限制，可以填任意多个极长 $1$ 连续段，最后填一个任意长度 $1$ 连续段。

此时发现，若还要填 $0$ 的连续段，那么需要将所有 $1$ 旁边的极长 $0$ 连续段填上，不如将上述 $0,1$ 交换操作。于是可以填的总共有：一个两边都是 $0$ 的 $0$，若干个极长 $1$ 连续段，一个任意长度 $1$ 连续段。然后再进行开头说的拓展。

于是可以 dp 了：设 $dp_{i,0/1,0/1,0/1/2/3}$ 表示当前处理到第 $i$ 位，两边都是 $0$ 的 $0$ 是否使用过，任意长度 $1$ 连续段是否使用过，当前位置不标记/标记了但是后面组成极长 $1$ 连续段/是极长 $1$ 连续段的一部分/选且已经组成了极长 $1$ 连续段。讨论每一种转移即可。

[ARC110C] Exoswap (*1100)

依次找 $1,2,3,\cdots,n$ 往前操作即可。

[ARC110D] Binomial Coefficient is Fun (*2078)

非常有趣的组合意义。看到上指标和要求为 $m$，联想到范德蒙德卷积，考虑从组合意义入手看有没有很好的算法。

考虑这大概能表示成总共 $m$ 个位置选 $\sum a_i$ 个。但是发现若选的第 $a_1$ 个和第 $a_{1}+1$ 个位置中间有若干空位，则 $b_1$ 不是唯一确定的。然后发现可以通过加一个分隔符的方式确定。于是就变成了不超过 $m+n-1$ 个位置选 $s+n-1$ 个的方案数，根据经典上指标求和，答案即为 $\binom{m+n}{s+n}$。$O(s+n)$ 暴力算组合数即可。

[ARC110E] Shorten ABC $\color{blue}\Diamond$ (*2973)

看到这种两个字符合成一个，最后还要计数的问题，$\color{blue}\Diamond$ 可以构造一个关于 $S$ 的简单函数 $f(S)$，使得不管怎么操作 $f(S)$ 都不变，然后从这个不变中寻找性质。

对于 AGC027E，这个构造的方法就是令 $a\to 1,b\to 2$，$f(S)=\sum S_i \bmod 3$。一开始也想的是模意义下的东西，但是一直没想出来。直到想到异或，瞬间有如醍醐灌顶：令 $a\to 1,b\to 2,c\to 3$，设 $f(S)=\bigoplus S_i$，这样就成功构造出来了一个不变的 $f(S)$ 了。

于是，此时知道一个区间的异或和，就能知道这个区间可能合成什么字符。但是什么时候可以什么时候不能合成一个字符呢？显然异或和为 $0$ 和区间长度 $>1$ 且区间内 $S_i$ 全相等时不行。

其他情况是否一定可行？感性理解，可以归纳地证明：若一个区间不是上两种情况，一定就能分成两个不是上面两种区间的区间。

然后考虑进行一个最简单的 dp：设 $dp_i$ 表示 $S[1,i]$ 的方案数。求 $dp_i$ 时，先枚举最后一位是什么。根据对应的异或和，就可以知道可以从哪里转移过来。

此时就会有一个结论：对于一个位置 $i$ 和一个异或和 $x$，大部分情况下只会从最大的 $j$ 满足 $\bigoplus_{j<k\le i}S_k=x$ 转移过来。这是因为 $[1,j]$ 的答案会包含 $[1,j'](k<j')$ 的答案。

证明：设另一个 $[1,j']$ 也满足 $\bigoplus_{j'<k\le i}S_k=x$。令 $[1,j']$ 能拼出来长为 $m$ 的串 $t$，若 $t_m$ 和 $S[j+1,i]$ 不全相同，根据上面的结论，$t_m$ 拼上 $S[j+1,i]$ 一定能合成一个和 $t_m$ 相同的字符。否则，考虑先将 $S[j+1,i]$ 拼到 $t$ 后面，再找到从后往前第一个不同的位置记为 $p$，则反复合并 $p,p+1$，一定也能得到和 $t$ 相同的串。

为什么说大部分情况下呢？因为如果找不到上述 $p$ 就会有问题。此时 $i$ 就是会从这些 $j'$ 转移过来的。但是发现会有这种情况当且仅当 $[1,j]$ 全部相同且 $[1,i]$ 不全部相同。即 $j$ 是固定的。所以可以找到每一个 $j'$ 并记录下来，后面再从这里转移。

做完了。时间复杂度 $O(n)$。

[ARC110F] Esoswap (*2719)

首先可以发现，对于一个固定位置操作若干次大概是能使这个位置变成任意一个数的。于是有个猜测的做法：倒序枚举 $i$ 不断对 $0$ 操作直到 $P_0=i$，然后再操作一次使 $P_i=i$。

试了一下发现不太行。因为如果此时 $a_0=0$ 就怎么也动不了了。然后发现 $0$ 其实非常不好，但是发现，可以通过操作若干次数字 $n-1$ 的方式使 $P$ 循环位移，于是先不断操作 $n-1$ 使 $0$ 固定到 $P_{n-1}$ 的位置。

这一步似乎也可以通过不断操作位置 $n-1$ 做到。

然后考虑依次使 $n-2,n-3,\cdots,2,1$ 到 $0$ 再到对应位置。此时又发现一个问题：当 $P_0=n-1$ 的时候又会出问题。

但是发现这个时候好操作很多：只需要不断操作数字 $n-1$，使它去到还没归位的数的末尾。然后变成不断操作 $1$ 即可。再发生一次就变成不断操作 $2$，以此类推。

最后再不断操作数字 $n-1$，整个 $P$ 满足要求即可。

[ARC111C] Too Heavy (*1750)

若一个位置一开始就有 $a_i\le b_{p_i}$ 则一定无法操作。否则按 $b_i$ 从大到小，使 $b_i$ 一步到 $i$ 即可。

[ARC111D] Orientation $\color{blue}\nabla$ (*2064)

若 $c_u<c_v$ 则一定是 $v\to u$，否则 $c_u=c_v$ 的 $u,v$ 在同一个强连通块内。因为保证有解所以 dfs 一遍即可。

[ARC111E] Simple Math 3 $\color{blue}\triangle$ (*2541)

cnm 怎么是类欧，如果这辈子有幸学到类欧了就改这个题。

[ARC111F] Do you like query problems? $\color{blue}\Diamond\Box$ (*3119)

考虑拆贡献：设第 $i$ 次操作修改了位置 $x$ 的值为 $v$，使其在第 $j$ 次操作的查询贡献。

不妨令第 $i$ 操作为 $\min$，$i$ 之前最后一次 $\max$ 且 $v'>v$ 的操作位置为 $k$。则要满足以下条件：

• $[1,k-1]$ 内任意。

• $[k+1,i-1]$ 内，所有修改操作要不与 $x$ 不交，要不是 $\min,v'>v$ 或 $\max,v'\le v$。

• $[i+1,j-1]$ 内，所有修改操作要不与 $x$ 不交，要不是 $\min,v'\ge v$ 或 $\max,v'\le v$。

• $[j+1,q]$ 内任意。

四种情况分别有的方案数为：

• $(\frac{(2m+1)\times n\times(n-1)}{2})^{k-1}$

• $(m\times (x-1)\times(x-2)+m\times(n-x)\times(n-x-1)+m\times x\times(n-x+1)+\frac{n\times (n-1)}{2})^{i-k-1}$

• $(m\times (x-1)\times(x-2)+m\times(n-x)\times(n-x-1)+(m+1)\times x\times(n-x+1)+\frac{n\times (n-1)}{2})^{j-i-1}$

• $(\frac{(2m+1)\times n\times(n-1)}{2})^{q-j}$

再加上 $k,i,j$ 分别的方案数：

• $(m-v)\times x\times(n-x+1)$
• $x\times(n-x+1)$
• $x\times(n-x+1)$

所以答案即为 $\sum\limits_{i=1}^q\sum\limits_{j=i+1}^q\sum\limits_{k=1}^{i-1}\sum\limits_{x=1}^n\sum\limits_{v=0}^{m-1}(\frac{(2m+1)\times n\times(n-1)}{2})^{k-1}\times (m\times (x-1)\times(x-2)+m\times(n-x)\times(n-x-1)+m\times x\times(n-x+1)+\frac{n\times (n-1)}{2})^{i-k-1}\times (m\times (x-1)\times(x-2)+m\times(n-x)\times(n-x-1)+(m+1)\times x\times(n-x+1)+\frac{n\times (n-1)}{2})^{j-i-1}\times (\frac{(2m+1)\times n\times(n-1)}{2})^{q-j}\times (m-v)\times x\times(n-x+1)\times x\times(n-x+1)\times x\times(n-x+1)\times v$

令 $f(i)=(\frac{(2m+1)\times n\times(n-1)}{2})^{i-1},g(i)=(\frac{(2m+1)\times n\times(n-1)}{2})^{q-i}$

$A=(m\times (x-1)\times(x-2)+m\times(n-x)\times(n-x-1)+m\times x\times(n-x+1)+\frac{n\times (n-1)}{2}),B=(m\times (x-1)\times(x-2)+m\times(n-x)\times(n-x-1)+(m+1)\times x\times(n-x+1)+\frac{n\times (n-1)}{2})$

变成 $\sum\limits_{i=1}^q\sum\limits_{j=i+1}^q\sum\limits_{k=1}^{i-1}\sum\limits_{x=1}^n\sum\limits_{v=0}^{m-1}f(k)\times A^{i-k-1}\times g(j)\times B^{j-i-1}\times(x\times(n-x+1))^3\times (m-v)\times v$

$f(k)\times A^{i-k-1}$ 和 $g(j)\times B^{j-i-1}$ 分别可以在确定 $i,x$ 后分别可以 $O(n)$ 推出来对于所有 $i$ 的值。

变成 $\sum\limits_{i=1}^q\sum\limits_{x=1}^npre_i\times suf_i\times(x\times(n-x+1))^3\times \sum\limits_{v=0}^{m-1}(m-v)\times v$

---

以上是想的时候推的。但是很难优化。$\color{blue}\Diamond\Box$ 实际上问题在于，一开始就枚举 $i,j,k$ 使得整个过程过于复杂。需要考虑更好的性质。

考虑 $\sum[v=i]x=\sum[v\ge i]$。于是对于一个在第 $i$ 次操作，包含 $x$ 的询问，在其之前一定有一次 $\max \ge v$ 的操作 $j$。设其为最后出现的那一次。令 $A=\frac{(2m+1)n(n+1)}{2},f(i)=A-mi(n-i+1)$ 则答案为：

$\sum\limits_{v=1}^{m-1}\sum\limits_{i=1}^q\sum\limits_{j=1}^{i-1}\sum\limits_{x=1}^nA^{j-1+q-i}f(x)^{i-j-1}x^2(n-x+1)^2(m-v)$

发现这只和 $i-j$ 有关：

$\sum\limits_{v=1}^{m-1}\sum\limits_{l=1}^{q-1}\sum\limits_{x=1}^nA^{q-l-1}f(x)^{l-1}x^2(n-x+1)^2(m-v)(q-l)$

主意到只有 $m-v$ 这一项和 $v$ 有关：

$\frac{m(m-1)}{2}\sum\limits_{l=1}^{q-1}\sum\limits_{x=1}^nA^{q-l-1}f(x)^{l-1}x^2(n-x+1)^2(q-l)$

把 $x$ 提前：

$\frac{m(m-1)}{2}\sum\limits_{x=1}^nx^2(n-x+1)^2\sum\limits_{l=1}^{q-1}A^{q-l-1}f(x)^{l-1}(q-l)$

提出来 $A$：

$\frac{m(m-1)}{2}A^{q-2}\sum\limits_{x=1}^nx^2(n-x+1)^2\sum\limits_{l=0}^{q-2}(\frac{f(x)}{A})^l(q-l+1)$

再处理一下：

$\frac{m(m-1)}{2}A^{q-2}\sum\limits_{x=1}^nx^2(n-x+1)^2(\sum\limits_{l=0}^{q-2}(\frac{f(x)}{A})^l(q+1)-\sum\limits_{l=0}^{q-2}(\frac{f(x)}{A})^ll)$

后面的式子前半部分直接做。后半考虑：

$S=\sum\limits_{i=0}^nix^i$

$xS=\sum\limits_{i=1}^{n+1}(i-1)x^i$

$(x-1)S=nx^{n+1}-\sum\limits_{i=1}^nx^i=nx^{n+1}-\frac{x^{n+1}-x}{(x-1)}$

于是最后的式子就是 $\frac{nx^{n+1}-\frac{x^{n+1}-x}{(x-1)}}{x-1}$。做完了。

[ARC112C] DFS Game (*1913)

答辩题。

考虑进入 $u$ 所在子树后，一共要走 $3siz_u$ 步才能出来。一开始显然先手能拿硬币，若进入了一个大小为 $siz_v\bmod 2=1$ 的子树，则会交换先后手，否则不变。于是分讨：

• 有奇数个大小为奇数的子树，则最后一定是后手能获得若干个偶数大小子树的先手。但是其中有些贡献为负，又发现这些其实可以在前面就丢给先手。于是奇子树轮流取最大，偶子树给先手造成 $|w|$ 的贡献。
• 有偶数个大小为奇数的子树，则所有偶子树都会被先手取到先手。直接转移。

树上 dp 即可。

[ARC112D] Skate (*2028)

我们称一个位置对于 $(x,y)$ 为可达的，当且仅当从 $(x,y)$ 开始，可以移动并停在这里。那么容易发现，可达是双向的且具有传递性，且所有点都可达 $(1,1)$。于是题目的要求可以转化为，要求从 $(1,1)$ 开始可以经过所有位置。

考虑若一个点能被经过，它所在的行或列一定有一个点对于 $(1,1)$ 可达。进一步，发现在边不在角上的可达位置是没有意义的。然后题目要求变成每一行或列一定有一个点对于 $(1,1)$ 可达。而两个对于 $(1,1)$ 可达的点直接相连的要求即为在同一行或列。于是运用经典套路，对于一个 # 或者角，将行和列相连，则答案为连通块数 $-1$。

[ARC112E] Cigar Box (*2659)

首先，把 $a_i=i$ 的序列 $a$ 变成给定序列显然是难做的，考虑将目标序列进行某种映射，转化成将 $a$ 变成 $a_i=i$。

然后发现，对于每个数字，只有对其的最后一次操作是有用的，并且进行放到开头的操作的数字一定是某个 $[1,i]$ 内的所有数，并且依次进行 $i,i-1,i-2,\cdots,1$ 的操作。放到末尾的同理。

于是考虑倒推每次操作，就变成了依次对 $1,2,\cdots,x$ 操作。并且对 $i$ 进行操作后，以后可以任意对 $i$ 操作。

则可以进行 dp：设 $dp_{i,j,k}$ 表示当前到第 $i$ 次操作，已经进行过放到第一的操作的为 $[1,j]$，进行过放到末尾的为 $[k,n]$ 的方案数。则转移为：$dp_{i,j,k}=dp_{i-1,j-1,k}+dp_{i-1,j,k+1}+(j+n-k+1)dp_{i-1,j,k}$。而对于没有进行过操作的数，它们之间的相对位置不变，则检查它们的相对位置是否符合条件即可。

这是 $O(n^3)$ 的。考虑优化状态。发现 $j$ 和 $k$ 无关，于是考虑记录 $[1,j]$ 和 $[k,n]$ 这些一共选了多少个，最后在乘上 $\binom{j+n-k+1}{j}$。状态为 $dp_{i,j}$ 表示前 $i$ 次操作，已经进行过操作的位置有 $j$ 个，则有转移：$dp_{i,j}=dp_{i-1,j-1}+2jdp_{i-1,j}$。

最后枚举 $j,k$，判断 $[j+1,k-1]$ 是否符合条件，再乘上上述组合数，全部情况相加即可。时间复杂度 $O(n^2)$。

咕咕咕，最近脑子不太好使啊。

[ARC112F] Die Siedler $\color{blue}\triangle\Diamond$ (*3432)

为什么会一点思路没有呢？

首先，显然是可以做完所有 $1$ 操作再做 $2$ 的。然后考虑如果已知进行完 $1$ 操作后的局面为 $A$，$A$ 最后最少剩 $F(A)$ 张牌，则 $F(A)$ 可以任意操作可以操作的位置直到不能操作，这样贪心求得。$\color{blue}\triangle$为什么 $2$ 操作的顺序不会影响结果？我不知道我不知道我不知道我不知道我不知道我不知道我不知道我不知道。

但是发现如果记录整个 $A$ 的状态会要记录很多东西，于是尝试简化状态。$\color{blue}\triangle\Diamond$ 考虑倒换 $[2,n]$ 内的数，全部换成 $1$，具体地，一共会换出来 $\sum c_i2^{i-1}(i-1)!$ 张 $1$。于是就可以这样表示一个状态。并且发现可以用 $2^nn!$ 张牌转一圈，变回一个 $1$。

然后再考虑进行完所有 $1$ 操作的 $A$ 的 $c_1$ 可能值是多少。设其为 $T$，初始状态为 $S$，每个卡包状态的 $c_1$ 为 $a_i$，选 $x_i$ 包，则有：$T=S+\sum a_ix_i-y(2^nn!-1)$。发现这是一个不定方程的形式，考虑裴蜀定理，于是设 $g=\gcd(\gcd_{i} a_i,2^nn!-1)$，则 $S\equiv T\pmod{g}$，接下来要做的就是对于所有可能的 $S<2^nn!$，求出 $\min f(S)$。

$\color{blue}\triangle$ 考虑根号分治。若 $g\le \sqrt{2^nn!}$，则将问题转化成 $\sum x_i2^{i-1}(i-1)!\equiv S\pmod{g}$，同余最短路解决。否则暴力枚举所有可能的 $T$，每个贪心算。由于某些没有意义的复杂度分析所以这是对的。

[ARC113C] String Invasion (*829)

从后往前贪心即可。

[ARC113D] Sky Reflector $\color{blue}\nabla$ (*1389)

不难发现 $\max a_i\le \min b_i$，于是枚举 $\max a_i$ 的值然后算即可，特判 $n,m=1$。

[ARC113E] Rvom and Rsrev (*2789)

小清新分讨。

注意到尽可能不会删 b，所以先考虑 a 怎么删。手玩容易得到，若 $cnta\bmod 2=0$ 或 $s_n=a$ 则一定能只删 a 删成 bbb...bbaaa..aa 这样的形式，由于 b 数量不变，a 数量每次减少 $2$，问题就变成了如何最小化步数。

这种问题一般会从连续段数量上看。于是考虑什么样的操作会减少 b 连续段数量。考虑若 $s_{i-1}=s_{j-1}=b$，则操作 $(i,j)$ 后这两段会并在一起，于是用一次操作能减少一段。还有呢？若 $s_{i-1}=s_{i+1}=s_{j-1}=s_{j+1}=b$，一次减少两段。于是先尽可能操作后者，剩下操作前者，次数容易算出。这里有一个特殊情况，若 $s_1=a$，那么应该视作 $s_0=b$，再判断连续段数。

然后考虑剩下的情况。这些情况删完之后中间一定会剩一个 a，设其在 $p$，则可以操作 $(p-1,n)$ 将这个 $1$ 换到最后。此时又有两种特殊情况：

• 只有开头 $s_1=a$ 的一段。此时开头一定会剩一个 a。
• 只有结尾 $s_{n-1}=a$ 或 $s_{n-2}=a$ 的一段，此时容易发现对其进行上面的操作反而更劣，于是消掉所有其它的 a 然后不操作。

剩下的情况就转化成，先同上用尽可能少的操作消成两个连续段，再进行一次操作把 a 换到后面。此时又有最后一种特殊情况：若除了 $s_{i-1}=s_{i+1}=s_{j-1}=s_{j+1}=b$ 的情况只有 $s_1=a$ 对应的开头一段，容易发现是需要用一个 $s_{i-1}=s_{i+1}=b$ 的位置消掉开头的。

然后就做完了。

[ARC113F] Social Distance $\color{blue}\triangle\Diamond$ (*3990)

不会积分，改不了，但是感觉大概懂了。

先考虑如果只是整数怎么做。考虑经典求期望套路 $E(x)=\sum P(x\ge i)$，转化成每两个距离都大于 $lim$ 的概率。$\color{blue}\Box$ 注意到此时x_i形如每个变量有个取值范围，大小有限制，于是尝试转化成经典模型，要求 $a_i\in [x_{i-1}-(i-1)lim,x_i-(i-1)lim]$ 且 $a_i$ 不减。这是类似上面做过的 [ARC104E] Random LIS 的模型（当然这题做法就不能指数了）。

考虑离散化后设 $dp_{i,j,k}$ 表示考虑到第 $i$ 段值域区间，当前为第 $j$ 个变量，这段区间已经选了 $k$ 个，转移分当前变量在/不在当前区间并处理概率即可。

然后拓展到实数，$\color{blue}\Box\Diamond$ 注意到这个方程只和每个 $[x_{i-1}-(i-1)lim,x_i-(i-1)lim]$ 之间大小关系有关，一共 $O(n^2)$ 种大小关系，$\color{blue}\triangle\Diamond$ 并且对于每种大小关系，离散化后区间的真实长度 $len$ 是一个关于 $x$ 的一次函数，所以最后结果也会是一个关于 $x$ 的多项式，做一些积分相关即可。不会了。/kk

也是缓慢地搞定了 10 rounds。

[ARC114C] Sequence Scores (*2056)

首先分析，如果现在已知 $A$，怎么求 $f(A)$。首先贪心地想，设依次操作 $v_i$，若 $v_{i+1}<v_i$，那么换成先操作 $v_i$ 再 $v_{i+1}$ 一定不劣，因为可能的结果后者包含前者。于是一定是按 $v$ 从小到大操作。

然后发现，对于一个 $a_i=a_j=x$，若 $\exists k\in(i,j),a_k<x$，则无法用一次操作同时使 $a_i,a_j$ 满足要求，否则会影响中间已经确定的数。同时，若 $a_i$ 这个数是第一次出现，显然也要一次操作。

然后拆开算贡献。对于第一种情况，考虑枚举 $a_i=k$ 上一次出现的位置为 $j$，则 $(i,j,k)$ 产生贡献的要求有：$(i,j)$ 中没有 $k$ 且 $\exists p\in(i,j),a_p<k$。计算方案数，考虑算没有 $k$ 的方案减去全 $>k$ 的方案，为 $((m-1)^{i-j-1}-(m-k)^{i-j-1})m^{n-i+j-1}$，后面的 $m$ 是其他位置任取的方案数。于是方案数为：

$\sum\limits_{i=1}^n\sum\limits_{k=1}^m\sum\limits_{j=1}^{i-1}((m-1)^{i-j-1}-(m-k)^{i-j-1})m^{(n-(i-j+1))}$

然后推式子。发现只和 $i-j$ 有关：

$=\sum\limits_{i=1}^{n-1}\sum\limits_{k=1}^m((m-1)^{i-1}-(m-k)^{i-1})(n-i)m^{n-i-1}$

改变枚举顺序。

$=\sum\limits_{k=1}^m\sum\limits_{i=1}^{n-1}((m-1)^{i-1}(n-i)m^{n-i-1}-(m-k)^{i-1}(n-i)m^{n-i-1})$

对于 $x^iy^{n-i}$ 状物，有个 trick 是提出来 $y^n$ 变成 $y^n(\frac xy)^i$。

$=m^{n-2}\sum\limits_{k=1}^m\sum\limits_{i=1}^{n-1}((\frac{m-1}{m})^{i-1}(n-i)-(\frac{m-k}{m})^{i-1}(n-i))$

$=m^{n-2}(n\sum\limits_{k=1}^m\sum\limits_{i=1}^{n-1}((\frac{m-1}{m})^{i-1}-(\frac{m-k}{m})^{i-1})-\sum\limits_{k=1}^m\sum\limits_{i=1}^{n-1}(i(\frac{m-1}{m})^{i-1}-i(\frac{m-k}{m})^{i-1}))$

发现前半部分是等比数列形式，可以 $O(1)$ 算。后半形似 $\sum (i+1)x^i$，对于这种的处理，令 $A=\sum\limits_{i=0}^n (i+1)x^i,xA=\sum\limits_{i=1}^{n+1} ix^i$，相减得 $(x-1)A=(n+1)x^{n+1}-\sum\limits_{i=0}^nx^i$，结合等比数列也是 $O(1)$。

于是 令 $f(x,n)=\sum\limits_{i=0}^nx^i=\frac{x^{n+1}-1}{x-1},g(x,n)=\sum\limits_{i=0}^{n}(i+1)x^i=\frac{(n+1)x^{n+1}-f(x,n)}{x-1}$，则有：

$=m^{n-2}(n\sum\limits_{k=1}^m(f(\frac{m-1}{m},n-2)-f(\frac{m-k}{m},n-2))-\sum\limits_{k=1}^m(g(\frac{m-1}{m},n-2)-g(\frac{m-k}{m},m-2)))$

此时 $O(n\log n)$ 已经是简单的，至于 $O(n)$，容易发现需要快速幂的只有 $x^{n-1}$，线性筛预处理，再预处理一些逆元即可。

后面部分的式子比较简单，为 $\sum\limits_{i=1}^n\sum\limits_{k=1}^m(m-1)^{i-1}m^{n-i}$。容易发现与 $k$ 无关，于是动态维护后面两个东西即可。

[ARC114D] Moving Pieces on Line $\color{blue}\Diamond$ (*2723)

先尝试分析一些简单的性质。

首先，每个棋子可以视作只往一个方向移动若干距离，因为这个操作相当于原本边权为 $0$，每走一步将边权 $\oplus1$。显然走回头路会抵消掉之前走的。也就是说，可以将问题转化成，对于每个 $a_i$ 选择一个 $b_i$，将 $[a_i,b_i]$ 间的边权 $\oplus 1$，使得最后的边权序列满足要求。

其次，棋子移动的终点一定是原本的某个 $a_i$ 或者 $x_i$。否则，可以通过调整变成这种情况并且不劣。称这些点为关键点。

此时其实可以写出一个 $O(n^4)$ dp：设 $dp_{i,j,k,l}$ 表示包含第 $i$ 个关键点的区间，设当前位置为 $x$，有 $j$ 个的 $a_i<x$，$k$ 个的 $a_i>x$，还有 $l$ 个没有确定。转移甚至可能还不是 $O(1)$ 的，但是显然不对。

先尝试优化，可能会根据想到进行一些分讨，但是看着就不太行。于是再考虑进行转化。$\color{blue}\Diamond$ 仔细想想，区间异或，只有若干个关键点，会想到？对了，差分！

考虑把操作和限制都转化成差分数组上的。操作变成，每次选择 $a_i$ 和任意一个位置 $\oplus 1$，限制变成，要求最后若干个位置是 $1$。于是可以得到还有若干个位置需要 $\oplus1$，而对于若干个可以任意选择的位置，要不两两匹配，要不找一个还需要 $1$ 的位置匹配。

于是把 $a_i$ 和需要 $1$ 的位置放在一起排序后 dp：设 $dp_{i,j,0/1}$ 表示到了第 $i$ 个位置，当前还有 $j$ 个没有匹配，并且没有匹配的是 $a_i$/需要 $1$ 的位置。容易证明两种不会同时没有匹配，因为这样的话在前面就先匹配上更优。转移是 trivial 的，使用一些费用提前计算的技巧即可。

于是时间 $O(n^2)$，空间滚动后 $O(n)$ 通过了这题。

[ARC114E] Paper Cutting 2 $\color{blue}\nabla$ (*2514)

首先可以把切开视作缩小边界但不去掉。然后考虑一个序列 $p$ 表示所有的线依次什么时候被操作。因为被操作两次显然没有意义所以这是个类似排列的东西。

然后根据期望的线性性，分开每条线算贡献。考虑如果是两个黑点围成的矩形左边的线，如果它在 $p$ 中的位置在它左边的所有线以及会导致结束的线之前，则会对答案产生 $1$ 的贡献。设这些线共有 $cnt$ 条，则只考虑这 $cnt$ 条加上当前考虑的一条线在 $p$ 中的相对顺序，于是该线位置最前的概率为 $\frac{1}{cnt+1}$。则答案为 $\sum \frac{1}{cnt+1}$。

[ARC114F] Permutation Division (*3545)

板刷 ARC 就是为了做出这种题。/zhq

先手玩一下，看看两边会如何操作。首先，设分成第 $i$ 个段的第 $j$ 位为 $b_{i,j}$，那么对方肯定会贪心地把 $b_{i,1}$ 最大的 $i$ 段给放到开头，而所有的 $b_{i,1}$ 不相同，所以设最后对方放的第 $i$ 个段的第 $j$ 位为 $c_{i,j}$，则 $c_{1,1}\ge k$。所以我方就要贪心地，使 $b_{i,1}$ 取到当前剩下的最小的 $k$ 个数。

但是不一定能取到，因为会发现，如果当前 $a_1=x$，则一定存在一个 $b_{i,1}=x$。若此 $x$ 比剩下最小的 $k$ 个数中最大的还大，则一定有 $c_{1,1}=x$，剩下的 $c_{i,1}$ 依次为剩下最小的 $k-1$ 个数。

并且还有一个性质，就是答案的字典序不会比原序列小，否则对方就直接不操作。

分析出来这些就考虑怎么一段一段取，每取一段变成一个子问题。设上面两种情况分别为情况一和二，容易发现，如果出现上面的第一种情况，则剩下序列的开头位置字典序一定会变小。于是贪心地，我们就要尽可能使用情况二，剩下不能为情况二的再用一。

再来分析一下如何能取到情况二。设当前段开头为 $x$，下一段开头在 $i$ 取 $y$，还要取 $k$ 段。首先有 $x>y$，否则对方会选择把 $y$ 换到前面。并且有 $\sum_{j>i}[a_j<y]\ge k$，否则剩下的一定会有段头 $>y$ 的。

然后还需要做一个观察：如果确定了 $y$，那么 $y$ 之前取的组的数量越多越好。这是因为，根据上面的结论，若剩下还没取的有 $k$ 段，则下一个组的段头就是剩下数中第 $k$ 小的，显然 $k$ 越小越好。同时，我们现在只确定了 $y$，没有确定段的右端点。但也容易发现，这个右端点越大越好。这是因为设下一段开头位置为 $p$，则 $p$ 位置的字典序一定发生变化，于是这个位置越往后越好。

此时就可以开始处理了。首先对于 $x>y$ 的条件，又是越多越好且没有其他限制，于是发现，令情况二最后一段的段头位置为 $i$，则情况二取到的段数就是，钦定开头为 $a_1$，结尾为 $a_i$ 的最长下降子序列长度。找完 $i$ 后要找情况一的第一段的段头，设还要取 $k$ 段，这个位置就是最大的 $j$，满足 $\sum_{l>j}[a_l<a_i]\ge k$。

于是就依次维护这两部分。第一部分显然简单 SGT 维护。第二部分，将第一部分处理出来的每个 $i$ 和 $k$ 离线下来，考虑按照 $a_i$ 从小到大排序，依次标记每个位置 $a_i$ 的位置为 $1$，SGT 上二分找到最后一个后缀和 $\ge k$ 的位置 $p$，若 $p>i$ 则更新答案。令答案为一个二元组 $(x,y)$ 表示 $[x,n]$ 的分段用情况一，还要分 $y$ 段。于是最后答案就是在 $x$ 最大的基础上，使 $y$ 尽可能小的 $(x,y)$。最后输出答案就直接输出 $[1,x-1]$ 的 $a_i$ 以及对 $[x,n]$ 做情况一的结果即可。时间复杂度 $O(n\log n)$，结束。

对的，感觉这题就是常规的贪心，分析性质，甚至没有 Diamond。

[ARC115C] ℕ Coloring (*706)

从小到大模拟即可。

[ARC115D] Odd Degree $\color{blue}\Box\Diamond$ (*2325)

挺 tricky 的，没想出来。

$\color{blue}\Box\Diamond$ 对于这种异或为 $1$ 或者和奇偶性相关的，以及其他一些类型计数题目，会有很多条件无用，因为只要其中一部分条件就可以调整出一个合法的解。

对于这题，考虑拎出一棵生成树，钦定其中 $k$ 个点度数为奇数。容易发现，对于每一种非树边是否取的方案，都会有一种选取树边的方案使得满足要求。具体地，从下往上，若当前点不符合要求，则选取往父亲的树边，否则不选，这样一定有解。于是方案数为 $\binom nk2^{m-n+1}$。

对于有多个连通块的进行一个背包即可。

[ARC115E] LEQ and NEQ (*2363)

很套路的题，但是有意思就有意思在不同的解法挺多的。

Sol 1

考虑容斥，设 $dp_i$ 表示 $[1,i]$ 的答案，枚举 $[j,i]$ 内 $x_i$ 全部相同，则有 $dp_{i}=\sum (-1)^{i-j}dp_{j-1}\min_{j\le k\le i}a_k$。一个很套路的做法是枚举中间最小值分治，若 $i-l_i<r_i-i$ 则枚举左边，差分更新右边，否则枚举右边，用左边的前缀和更新。$O(n\log n)$。

Sol 2

还是同样的 dp 式子，但是发现确定 $\min$ 的位置后只和一段的 dp 值乘上 $(-1)^k$ 有关，于是维护一个单调栈，对于里面的每个元素 $b_i$ 维护 $(b_{i-1},b_i]$ 内可能的 $(-1)^jdp_{j-1}$ 之和记作 $c_i$ 与 $\sum c_ia_i$，每次新往最后加入一个元素就合并若干段并动态维护那几个值。$O(n)$。

Sol 3

考虑直接 dp，设 $dp_{i,j}$ 表示第 $i$ 位选 $j$，则 $dp_{i,j}=\sum dp_{i-1,k}-dp_{i-1,j}$。于是要支持区间加，区间乘，线段树维护即可。$O(n\log n)$。

[ARC115F] Migration (*3336)

考虑如果当前有一个状态 $A$ 能在和不超过 $lim$ 的前提下到达一个状态 $B$，则 $B$ 在同样条件的前提下也能到达 $A$。

于是对于初始状态 $S$，会发现最优策略一定是先把和变得尽可能小，达到状态 $R$，以此让某些要经过很大值的点通过，然后再变成结束状态 $T$。

如果我们想知道一个状态 $A$ 在操作过程中和不超过 $lim$ 的前提下，和尽可能小的状态 $B$ 是简单的。考虑记录 $d_{i,j}$ 表示一个棋子从 $i$ 点移动到 $j$ 点，其他不动，会使和 $s$ 增加多少。

容易发现我们只会把棋子从 $h_i$ 大的移动到 $h_i$ 小的。同时，若 $dis_{i,j}<dis_{i,k}$，先移动到 $j$ 一定不劣。于是对于每个位置 $u$，下一次会移动到的点 $to_u$ 是固定的，只需要每次找可移动的点移动即可。一共会移动 $O(n^2)$ 次，使用优先队列优化后这一部分是 $O(n^2\log n)$ 的。

但是此时又发现一个问题：求 $R$ 是否能到达 $T$ 是困难的。但是由于一开始给出的结论，考虑对于 $T$ 求出它能到达的和最小的状态 $R'$，于是只用求 $R$ 是否能到达 $R'$。

这个判断是简单的，容易发现，若 $R$ 和 $R'$ 中两个对应的棋子的 $h$ 不同，则一定无解。因为若 $R$ 中的 $h_x$ 小于 $R'$ 中的 $h_y$，那么说明这个 $x$ 无法到达 $y$，否则 $R$ 会变化。于是只用判断此时 $R$ 的和 $sum$ 是否有 $sum+\max dis_{x,y}\le lim$ 即可。

同时这个 $lim$ 显然是可二分的，所以二分答案，复杂度为 $O(n^2\log V\log n)$。

然而此时大概率还无法通过。于是卡卡常，首先是发现设 $S,T$ 的和分别为 $s,t$，则二分边界可以设成 $l=\max(s,t),r=l+10^9$。同时，发现 at 的 c++17 比 c++20 要快。于是 3900ms 通过。

话说好像不用二分，就不卡常了。

[ARC116C] Multiple Sequences (*1468)

方案数显然只与序列中出现了多少个不同的数有关，而且这显然是 $O(\log n)$ 级别的，于是 dp 出每种数量的情况数即可。

[ARC116D] I Wanna Win The Game (*1718)

显然拆位后变成每一位都选偶数个 $1$，于是 dp 记录当前和为 $j$ 的方案数即可，每次转移枚举这层选多少然后乘组合数。

[ARC116E] Spread of Information (*2236)

首先显然可以二分，然后就变成求最少要用多少个关键点。贪心地，dfs 从底往上做，显然是直到不得不放了才放一个关键点。于是设 $d_u$ 表示 $u$ 离下面最近的关键点的距离，注意一个 $u$ 的两个儿子 $v_1,v_2$ 之间的 $d$ 可能会互相影响。

[ARC116F] Deque Game $\color{blue}\Box\Diamond$ (*3125)

$\color{blue}\Diamond$ 首先是之前见过的结论。若 $k=1$，设 A 先手，$p=\left\lfloor\frac{n+1}{2}\right\rfloor$，若 $n$ 为奇数则最后剩下 $\min(a_p,\max(a_{p-1},a_{p+1}))$，否则剩下 $\max(a_p,a_{p+1})$。后手类似。$\color{blue}\Box\Diamond$
但是这里还能引申出一个很有意义的结论：当 $n$ 为奇数时都是后手优势，否则先手优势。

于是对于这题，对于 $n$ 为奇数的序列，两边都不会去碰，否则，两边会轮流选择 $n$ 为偶数的序列，进行一次操作变成奇数的。设这样操作后这个序列能变成的最大结果为 $x$，最小为 $y$，则按照 $x-y$ 排序，两边依次选。最后再求出所有最后得到的数即可。

[ARC117C] Tricolor Pyramid (*1768)

估计是把 ARC110E 的不可行做法搞过来出了个题。考虑 ABC 分别为 012。则每次操作会产生一个 $-(x+y)\bmod 3$。但是发现仍然不能暴力维护，于是考虑对于每个位置计算贡献。正负性显然是确定的，系数还要乘上一个组合数 $\bmod 3$，lucas 搞一搞就行。

[ARC117D] Miracle Tree $\color{blue}\nabla\Diamond$ (*2115)

好离谱，感觉这个题给我一年我都不一定做得出来……考虑将每个点放入一个序列中，发现只要相邻两个满足条件，全部条件也就满足。因为 $dis(i,j)+dis(j,k)\ge dis(i,k)$。于是全部取等得到 $E_n=\sum dis(a_i,a_{i+1})+1\le 2(n-1)-dis(a_1,a_n)+1$。显然也可以取等，于是就让 $dis(a_1,a_n)$ 取 $\max$，为直径。

感觉这种只找相邻两个的关系的技巧还挺多见的，反正最近被一个纸张题创了。

[ARC117E] Zero-Sum Ranges 2 $\color{blue}\nabla$ (*3166)

若已知最终序列，考虑如何快速求 $\sum\limits_{l\le i\le r} a_i=0$ 的个数。显然可以求出前缀和数组 $s$，则设 $c_i$ 为 $\sum_js_j=i$，则个数为 $\sum \binom{c_i}{2}$。

然后考虑计数。因为只有 $+1,-1$ 于是转化成折线图上每一层的问题。又因为是一层一层的，所以（好像真的）不难想到从上往下每一层进行连续段 dp。设 $dp_{i,j,k}$ 表示已经填了 $i$ 个位置，当前已经有 $j$ 对 $s_x=s_y$，当前层有 $k$ 个间隔，则转移为 $dp_{i,j,k}\to dp_{i+l,j+\binom l2,l-k-2}$。最后只需要把 $\ge 0$ 部分的和 $<0$ 的合并即可。

这里暂时空着一下，明天再写。

[ARC118C] Coprime Set (*1151)

首先先确保 $\gcd_ia_i=1$，构造 $6,10,15$ 三个数就行。然后把是其中至少一个的倍数的输出，发现是够的。

[ARC118D] Hamiltonian Cycle (*2448)

首先先搜出来只进行 $\times a$ 或 $\times b$ 能进行多少次。若 $=p-1$ 就直接结束。否则设分别 $x,y$ 次，则建所有 $i\to ai\bmod p$ 的边，容易发现这样会形成 $\frac{p-1}x$ 个大小为 $x$ 的环。于是现在问题就变成了，如何利用 $i\to bi\bmod p$ 的边到达并遍历所有的环。

首先考虑无解的情况，容易发现，走 $\frac x{\gcd(x,y)}$ 次 $a$ 的边会等价于走 $\frac y{\gcd(x,y)}$ 次 $b$ 的，因为重复 $\gcd(x,y)$ 次这样的操作都会走会起点。而这 $\frac y{\gcd(x,y)}$ 次操作一定会到不同的环上，否则这个值会变小。于是，若 $\frac{xy}{\gcd(x,y)}<p-1$ 则一定无解。

否则就直接考虑构造。考虑先把每个环经过一遍，最后再在回溯时遍历每一个环。具体路径就是 $1\to \frac 1b\to\frac 1{b^2}\to\cdots\to \frac 1{b^{\frac nx-1}}\to \frac a{b^{\frac nx-1}}\to \frac {a^2}{b^{\frac nx-1}}\to\cdots\frac {a^{x-1}}{b^{\frac nx-1}}\to \frac {a^{x-1}}{b^{\frac nx-2}}\to \frac {a^{x-2}}{b^{\frac nx-2}}\to\cdots$。这样一圈用 $\times a$ 跑，一圈用 $\times\frac 1a$ 跑。最后再回去 $1$ 即可。

[ARC118E] Avoid Permutations $\color{blue}\nabla$ (*3092)

不经过 $(i,P_i)$ 的限制直接做比较困难，容易想到套路容斥，钦定若干个 $i$，一定经过 $(i,P_i)$，再进行计数。则设 $dp_{i,j,k,0/1,0/1}$ 表示当前已经走到了 $(i,j)$，钦定了 $k$ 个点，这一行/列是否已经选了，则转移只用枚举这一步往右或网上走，以及如果这一列的 $P_i$ 没有给定，是否选下一个点即可。

感觉真挺简单的

[ARC119C] ARC Wrecker 2 (*1354)

容易发现若一个序列奇数位的和等于偶数位的和就可以消，前缀和一下就行。

[ARC119D] Grid Repainting 3 (*2713)

首先，若最后选了 $x$ 行 $y$ 列，则白色格子数为 $xm+yn-xy$。这个式子不太好求最值，所以考虑的方向就是枚举 $x$ 算 $y$ 最大值。

然后考虑如何判断一个方案是否合法，先套路化地在行和列之间连边，若 $(i,j)$ 为红色，则连 $(i,j+n)$ 的双向边，每条边都代表一个点，然后给每条边定向，若方向为 $u\to v$ 则表示，这条边操作的是 $u$，并且 $u$ 要比 $v$ 先进行操作，否则操作 $v$ 时会把这条边所代表的点染成白色。

于是就有结论：合法的操作中一定不会出现环，更进一步，会形成一棵内向树。若这个连通块不是一棵树，则任意选一棵生成树。并且根所代表的行/列不会被操作。也就是说，一个联通块内一定会有一个点不会被操作。同时又发现，我们不关心操作的行/列具体是哪些，只关心个数。

所以设一个联通块 $i$ 内代表行的点的个数为 $x_i$，列为 $y_i$。则对 $(x,y)$ 的贡献只可能是 $(x_i-1,y)$ 或 $(x_i,y_i-1)$，而且必须 $>0$。于是可以进行一个简单的背包 dp 解决。最后输出方案也是平凡的，只用对于每个连通块找到一个根，然后后序遍历生成树输出即可。

最近有在刷没在写，啥时候有空了多补一点。

[ARC119E] Pancakes (*2502)

其实这题怎么搞基本都能过，问题在于如何找到一个优美的实现方式。

首先显然翻转 $[l,r]$ 只会改变 $a_l,a_{l-1}$ 和 $a_r,a_{r+1}$ 两对。考虑绝对值的几何意义，即在数轴上的线段，有 $a<b,c<d$ 四个端点，显然不交的长度和小于相交，而回到原序列，相交当且仅当 $a_{l-1}<a_l,a_r<a_{r+1}$ 或反过来。

于是问题就变成求 $\max(\min(a_l,a_{r+1}))-\max(a_{l-1},a_r)),a_{l-1}<a_l,a_r<a_{r+1}$。考虑从大到小枚举 $a_i$ 作为 $a_l$，容易发现对换 $a_{l-1},a_l$ 和 $a_r,a_{r+1}$ 后结果不变，所以不需要考虑 $l<r$ 的限制。于是只需要最大化交集即可，即维护已经没枚举到的 $\min a_{i-1}$。求出最大交集即可。

[ARC119F] AtCoder Express 3 $\color{blue}\nabla\Diamond$(*3671)

其实没啥好写的发现 ABBBBBBA 这样，中间连续的 B 数量大于四个时，一定会直接从 A 跳过去，所以可以近似地看成 ABBBBA 类似，于是合法状态不多，$\color{blue}\Diamond$ 考虑建出一个自动机，分 13 种状态进行转移，然后就没了（

[ARC120C] Swaps 2 (*1478)

容易发现，$a$ 中的元素往前移动一位就会 $+1$，往后 $-1$，所以若最后 $a_i$ 与 $b_j$ 配对，则有 $a_i+i-j=b_j$ 即 $a_i+i=b_j+j$，于是就变成了求交换多少次能使 $a'=b'$，BIT 解决。

[ARC120D] Bracket Score 2 (*1996)

不难发现一个理论上界是 $a_i$ 中最大的 $n$ 个减去最小的 $n$ 个。考虑如何构造。若把最大的 $n$ 个看作 $+1$，其他 $-1$，则若前缀和始终 $\ge 0$ 就直接把 $+1$ 变成 (，$-1$ ）。但是不一定有这个性质，不过发现，如果前缀和出现负数，就把 $+1,-1$ 反过来，这样也是不会改变对应关系的。于是构造完了。

[ARC120E] 1D Party (*2653)

考虑令两个人相遇之后，不回头，而是将两个人身份调换，继续往同个方向走。

此时什么时候合法，发现若某个 $\ge i$ 的人和某个 $<i$ 的人相遇，则在原问题中 $i-1$ 和 $i$ 就一定会相遇，于是令最后 $i$ 和 $j$ 相遇，则每个 $[i-1,i]$ 的线段都至少被一对 $[i,j]$ 包含。于是考虑将若干 $[i,j]$ 之间配对，则答案为合法的配对方案中 $\max a_j-a_i$ 最小的。

此时又有一个观察：如果 $j-i$ 比较大，具体地如果 $>3$ 时，容易发现此时拆分成两个区间也是合法的，答案也更小。于是考虑 $dp_i$ 表示前 $i$ 条边已经被覆盖的最小代价，枚举转移当前的配对的长度即可。

[ARC120F] Wine Thief (*3094)

考虑固定一个 $i$ 算 $a_i$ 的贡献。如果直接枚举一边的个数就得到了讨论区里的式子，比较难做。于是就需要把两边放在一起考虑。

具体地，考虑当前既然钦定 $i$ 选了，那 $i+1$ 和 $i-1$ 都不能选，于是把 $[1,i-2]$ 和 $[i+2,n]$ 拼起来算选 $k-1$ 个的方案数。但是同时又发现，$i-2$ 和 $i+2$ 可以同时选。于是考虑在中间新插入一个元素，值为 $0$，再去算方案数。

此时又有一个问题：如果选了那个新插入的元素，那么实际上在原序列中就只选了 $m-2$ 个元素。于是考虑再容斥掉，减去一定选了这个元素，其他位置一共选了 $m-2$ 个的方案数。不难发现这是一个子问题。

于是考虑设 $Solve(x,y,k)$ 表示当前钦定要选的点左边（也就是类似上文的 $[1,i-2]$）还有 $x$ 个元素，右边有 $y$ 个，还要从中选 $k$ 个。则选中 $i$ 的方案数为 $Solve(i-2,n-i-1,m-1)$。$Solve$ 大概长这样：

int solve(int x,int y,int k){
	if(x>y){
		return solve(y,x,k);
	}
	if(!x){
		return binom(y-k+1,k);
	}
	return Mod(binom(x+y-k+2,k),mod-solve(x-1,y-1,k-1));
}

其中显然有无用信息，注意到每次组合数的值只和 $x+y$ 和 $k$ 有关，只有迭代次数和 $\min(i-2,n-i-1)$ 有关。于是简化一下，变成循环的形式就是：

int j=m-1,k=n-3,p=1;
for(j=m-1,k=n-3,p=1;j>=m-x+1;j--,p^=1,k-=2){
  if(p){
    sum=Mod(sum,binom(k-j+2,j));
  }else{
    sum=Mod(sum,mod-binom(k-j+2,j));
  }
}
if(p){
  sum=Mod(sum,binom(k-j+1,j));
}else{
  sum=Mod(sum,mod-binom(k-j+1,j));
}

其中 $j$ 为还要选的个数，$k$ 为当前序列长度，$p$ 表示正负性。

再发现 $i$ 只会限制代码中 $j$ 的范围。于是预处理 $f_i=\sum_{i\le j\le m-1}(-1)^{m-j+1}\binom{k-j+1}{j}$ 就可以把循环部分干掉了。

总复杂度 $O(n)$。

[ARC121C] Odd Even Sort (*1856)

考虑依次把 $1$ 到 $n$ 归位。对于 $i<n-2$ 的数，若当前操作能使 $i$ 往前一位则一直操作直到归位，否则一定能找到一个不会影响到 $i$ 的位置过掉一轮。 $i\ge n-2$ 的直接手玩一组构造即可。

[ARC121D] 1 or 2 (*2784)

首先有一个结论，就是我们一定会选连续的若干个数为单个填的数。证明考虑，如果 $a<b<c$，选了 $a,c$ 不选 $b$，考虑若和 $b$ 配对的是 $x$，则若 $x>0$ 则换成 $a,x$ 配对不劣，否则换成 $c,x$ 不劣（这个证明应该没问题吧）。

然后就考虑选了 $[l,r]$，其他的数怎么配对，不妨设 $l-1>n-r$，考虑 $a_1$，如果它和 $a_n$ 配对比 $a_{n-1}$ 劣的话，则 $a_n$ 若不和 $a_1$ 配对只会导致 $\max$ 值变大。所以又有一个重要结论：我们会先尽可能的让最小的和最大的匹配。

于是发现可能的匹配只有两种：$[1,l-1]$ 内的和 $[r+1,n]$ 内的匹配，剩下还没匹配的每次从两端取一个数出来匹配。容易 $O(n^2)$ 预处理。最后枚举 $[l,r]$ 每次 $O(1)$ 算即可。

[ARC121E] Directed Tree (*2645)

题目要求每个 $a_i$ 都不能经过至少一条边到 $i$。如果考虑对于一个 $i$，怎么样的 $a_i$ 合法，则会发现它可以是 $i$ 子树内的点，$i$ 的父亲的儿子的子树中，不包含 $i$ 的子树内的点……这很难处理。

于是考虑正难则反，容易发现对于一个 $i$，不合法的 $a_i$ 是它的祖先。这个性质非常好，于是容斥。

考虑树形 dp，$dp_{u,i}$ 表示 $u$ 子树内有 $i$ 个点的 $a_i$ 还没有被钦定为不合法，按照 $O(n^2)$ 树形背包的方法转移。先不管 $u$ 点，把儿子的背包合并。

然后加入 $u$ 点，此时首先可能有一个 $u$ 子树内的点 $v$，$a_v\to u$。乘上选点的方案数，于是 $dp_{u,i}=dp_{u,i}+dp_{u,i+1}\times (i+1)$。然后 $u$ 点一定还没有被钦定，$dp_{u,i}=dp_{u,i-1}$。

最后统计答案时，给每个没有钦定的 $u$ 随便定一个 $a_i$，方案数为阶乘，再乘上 dp 值和 $(-1)^{n-i}$ 即可。

[ARC121F] Logical Operations on Tree (*2940)

首先考虑如何判断是否合法。容易发现，若把所有 OR 边断开，剩下的连通块中若有至少一个最后会变成 $1$ ，则显然合法。充分性显然，考虑证明必要性，如果先对 OR 边操作，则发现两个连通块会形成一个连通块，但是如果这个连通块最后会变成 $1$，则原来的两个连通块也至少有一个会变成 $1$。

然后考虑计数。存在一个连通块为 $1$ 的方案不好算，但是可以算不存在的方案。设 $dp_{u,0/1}$ 表示当前处理到 $u$ 点，当前连通块内是否已经有了至少一个为 $0$ 的点。转移枚举这条边是 OR 还是 AND 以及儿子所在连通块情况即可。

[ARC122C] Calculator (*1818)

本来想到了正解做法但是脑子抽了（

我们考虑一个神秘的数：$\frac {\sqrt 5+1}2$。怎么得来的？我们倒着操作 $x+y$，希望每次操作后 $\frac{\max(x,y)}{\min(x,y)}$ 不变，则有 $x-1=\frac 1x$，解得 $x=\frac{\sqrt 5+1}2$。于是考虑最后 $y=\frac{\sqrt 5+1}2$，再操作回来。但是实际上这样有精度问题，于是枚举 $[y-10,y+10]$ 内的数尝试操作即可。

[ARC122D] XOR Game (*2331)

考虑丢到 trie 树上做，从高到低位枚举。若有偶数个当前位为 $1$ 的数，则答案这一位为 $0$，并且要把当前位为 $0$ 的和 $1$ 的分开做。否则答案这一位一定为 $1$，于是只用求在这一位为 $1$ 和这一位为 $0$ 的中各选一个，异或的最小值即可。

[ARC122E] Increasing LCMs $\color{blue}\nabla\Diamond$ (*2535)

感觉挺厉害的。考虑如果正着做，当前选的数显然会影响后面某个数是否可行。$\color{blue}\Diamond$ 于是考虑倒退，每次删掉一个数，这样就只用考虑当前删掉的数是否合法。并且后删显然是不劣于先删的，所以只需要每次找出一个能删的删就一定是最优策略。

然后考虑如何判断是否能删，$\color{blue}\Diamond$ 这等价于 $\gcd(\operatorname{lcm}_{j\not=i} a_j,a_i)<a_i$，即 $\operatorname{lcm}(\gcd_{j\not=i}(a_i,a_j))<a_i$。证明考虑对于一个质因数，前者相当于 $\min(\max a_j,a_i)$，后者相当于 $\max(\min(a_i,a_j))$，显然等价。于是，每次 $O(n^2\log V)$ 判断即可。

[ARC123D] Inc, Dec - Decomposition (*2143)

感觉 slope trick 运用的不太熟练啊。不过还是创过去了。

首先考虑题目中给出的限制即 $b_i\le b_{i+1},c_i\ge c_{i+1}$，因为 $b_i+c_i=a_i$，转化成 $b_{i+1}\ge\max(a_{i+1}-a_i,0)+b_i$。

然后观察到 $|b_i|+|c_i|\le|b_i+c_i|=|a_i|$，当且仅当 $b_i,c_i$ 同正负的时候取得等号，否则若 $b_i>\max(a_i,0)$ 会多出 $b_i-\max(a_i,0)$，若 $b_i<\min(a_i,0)$ 会多出 $\min(a_i,0)-b_i$。

然后就可以考虑暴力 dp 算最少多出多少。$dp_{i,j}$ 表示当前枚举到第 $i$ 个数，$b_i=j$ 的最小代价。则 $dp_{i,j}=\min_{k<j-\max(a_i-a_{i-1},0)} dp_{i-1,k}+c(i,j)$。$c(i,j)$ 是上面提到的多出的贡献。

考虑优化。容易发现对于一个 $i$，$c(i,j)$ 形如一条斜率为 $-1$ 的射线拼上一段 $y=0$ 的线段再拼上一条斜率为 $1$ 的射线。容易联想到 slope trick。

考虑设 $f_{i,j}=\min_{k<j-\max(a_i-a_{i-1},0)}dp_{i,k}$，维护 $f_i$。不难发现 $f_i$ 单调不增。考虑斜率为 $-1$ 的射线对 $f_i$ 的影响，显然就是在 $\min(a_i,0)-1$ 的位置插入了一个折点。对于斜率为 $1$ 的，若会影响到当前最小值的那一段，则会删掉最后一个折点，再在 $\max(0,a_i)-1$ 位置插入一个折点，同时令最左侧最小值的位置为 $p$，则使答案增加 $(p-\max(a_i,0)+1)\times 2$。

此外每次 $k<j-\max(a_i-a_{i-1},0)$ 也就是整体向右平移一段距离，打个标记维护即可。

[ARC124C] LCM of GCDs (*1495)

考虑先确定第一对怎么分配，可能的 $\gcd$ 值就一定是分配的数的因数，然后 $O(n)$ 检查能不能取到这个值即可。

[ARC124D] Yet Another Sorting Problem (*2008)

首先如果没有只能 01 之间交换的限制，之间连边找环就行。考虑加上这个限制，容易发现若一个环里面既有 $0$ 又有 $1$，则显然是可以直接搞定的。否则手玩发现可以将一个全 $0$ 环和全 $1$ 环放在一起做，一共额外用 $2$ 步，剩下的每个环也是额外 $2$ 步。

[ARC124E] Pass to Next $\color{blue}\Diamond$ (*3031)

考虑令 $f_i$ 为 $i$ 给 $i\bmod n+1$ 的球数，则每个 $\min f_i=0$ 的 $f$ 和 $b$ 之间构成双射，于是转化成求 $\sum\prod a_i-f_i+f_{i-1}$。

怎么算这个呢？如果是形如 $a_i-f_i$ 这样，每一位是独立的，就可以分别算然后乘起来。但是还和 $f_{i-1}$ 有关。把乘积用分配律展开，硬上 dp：设 $dp_{i,0/1,0/1}$ 表示当前枚举到第 $i$ 位，这一位的 $f_i$ 是否确定，当前是否已经 $\exists j,f_j=0$。

先算乘积的第一项为 $a_1$ 或 $-f_1$ 的时候的贡献。每一位有四种转移：

1. 这一位选 $a_i$。
2. 这一位选 $-f_i$ 且下一位不选 $f_i$。
3. 这一位选 $f_{i-1}$ 且上一位不选 $f_{i-1}$。
4. 这一位和上一位都选 $f_{i-1}$。

转移很冗长不展开讲，大概就是对于选了的 $f_i$，如果在 $1$ 个位置选了，就乘上 $\sum_{j\le a_i} j=\frac{a_i(a_i+1)}2$，在 $2$ 个位置选了就乘上 $\sum_{j\le a_i}j^2=\frac{a_i(a_i+1)(2a_i+1)}6$，如果没选，这个位置对乘积没有影响，但是对方案数有影响，所以也乘上 $a_i$ 或 $a_i+1$。

同时转移的时候要判断这一位是否有 $f_i=0$，这样的 $i$ 只有在它没有被选到的时候对乘积有影响，在转移的时候加上这个转移即可。

最后统计答案的时候用类似的方法，判断 $f_n$ 的情况即可。

然后算第一位选 $f_{i-1}$ 的贡献，容易发现 dp 转移时类似的，只用改变初始值即可。注意此时 $i=2$ 时的转移 $4$ 不能用。这样把所有贡献累加得到答案即可。

[ARC124F] Chance Meeting (*3246)

基本上是自己想出来了，但是亿眼丁真了最后一步加法卷积。

把 $n,m$ 都先 $-1$ 方便处理。首先不难证明两条路径的交一定是一行内连续的一段。于是考虑设 $f_{i,j}$ 表示钦定 $(i,j)$ 为两人第一次相遇的位置，走到 $(i,j)$ 的方案数。容易发现走到 $(i,j)$ 和从 $(i,j)$ 到终点本质上是相同的，所以答案即为 $\sum f_{i,j}\times f_{i,n-j}$。

第一次相遇的条件显然是不好直接做的，于是考虑进行一个容斥，先算 $g_{i,j}$ 表示两人在 $(i,j)$ 相遇的方案数，则 $g_{i,j}=\binom{n+2j}{n-i,i,j,j}$，则 $f_{i,j}$ 即为在 $(i,j)$ 相遇的 $g_{i,j}$ 减去在前面相遇再过来的方案，并且一定是在同一行相遇。考虑从 $(i,k)$ 到 $(i,j)$ 且中途不相遇的方案，钦定从 $(i,k)$ 开始的第一步是 A 走的，那么最后就是 B 走，中途 AB 不相遇，不难发现方案数为卡特兰数。

于是令 $h_i$ 表示卡特兰数第 $i$ 位，可以得到 $f_{i,j}=g_{i,j}-\sum_{k<j}g_{i,k}h_{j-k-1}$。状态太大了先优化状态，发现 $g_{i,j}$ 展开是 $\frac{(n+2j)!}{i!(n-i)!j!j!}$，不难发现对于不同的 $i$，式子是相同的，只需要乘上一个和 $i$ 有关的系数。从另一个角度来说，可以先考虑向右的移动，对于上下的移动，只要固定了移动的序列，同时也就确定了相遇所在的行，于是不妨只对 $i=n$ 求解，最后只需要乘上一个 $\binom{2n}n$ 即可。

于是式子变成了 $f_{i}=g_{i}-\sum_{j<i}g_{j}h_{i-j-1}$，这是个明显（但是我怎么没看出来？？？）的加法卷积形式，NTT 解决即可。

[ARC125C] LIS to Original Sequence (*1896)

首先 $p_1=a_1$，然后考虑第二位，这里可以插入一个尽可能小的数，但是后面只能接上 $a_2$，这样一直到 $a_m$，在它前后放所有剩下的即可。

[ARC125D] Unique Subsequence $\color{blue}\nabla$ (*2187)

好久之前做的典题。考虑 dp，如果 $a_j=a_i,j<i$，则以 $i$ 为结尾的子序列完全包含以 $j$ 结尾的，于是后面不再从 $j$ 转移。对于每个位置从所有可以转移的位置转移过来即可。

[ARC125E] Snack $\color{blue}\Diamond$ (*2874)

非常 educational 的题啊。考虑从网络流的方向解决，容易建立一个最大流模型：源点向每个零食 $i$ 连一条流量为 $a_i$ 的边，每个零食 $i$ 到小孩 $j$ 连一条流量 $b_j$ 的边，每个小孩 $j$ 向汇点连一条流量为 $c_j$ 的边。最大流显然就是答案。

但是这样 $O(nm)$ 条边显然无法直接跑最大流。$\color{blue}\Diamond$ 考虑最大流转最小割，类似模拟网络流，算这个最小割。先考虑 $a_i$，容易发现剩下的边的流量和割掉哪个 $a_i$ 无关，只和没割掉的 $a_i$ 的个数和 $b_j$ 有关。于是贪心地，一定会从小到大割 $a_i$。而对于每个小孩 $j$，设没有割掉的数量为 $cnt$，则还需要割掉 $\min(c_j,cnt\times b_j)$ 的边。从小到大枚举 $cnt$ 然后动态维护这个 $\min$ 的式子即可。

[ARC125F] Tree Degree Subset Sum $\color{blue}\nabla$ (*3541)

好牛逼的题，完全没有印象做过。

首先树的限制相当于 $\sum d_i=2n-2,d_i\ge 1$，全部 $-1$ 变成 $\sum d_i=n-2,d_i\ge 0$。

然后是结论：若 $i$ 个物品能凑出 $j$ 的价值，则对于一个固定的 $j$，可行的 $i$ 是一段区间。

证明考虑设有 $cnt$ 个 $0$，$l(j)\le i\le r(j)$，则若 $r(j)-l(j)\le 2cnt$ 即得证，因为 $l(j)$ 一定对应不选 $0$，$r(j)$ 全选。考虑上面的 $(i,j)$ 对，一定有 $j-i\ge -cnt$，因为只有 $cnt$ 个 $0$。同时，若有 $(i,j)$，则一定有 $(n-i,n-2-j)$，其同样满足 $n-2-j-n+i\ge -cnt$ 即 $j-i\le cnt-2$。于是就有 $j-cnt+2\le i\le cnt+j$，得证。

最后只用套路地进行一个背包求出 $l(j),r(j)$ 即可。由于 $\sum d_i=n-2$，所以不同的 $d_i$ 个数是 $\sqrt n$ 级别的，二进制优化多重背包即可。

随机分析一下复杂度：$\sum_{i<\sqrt n} d_i=n-2$，则 $\sum_{i<\sqrt n} \log d_i\ge\sqrt n\log \sqrt n=\frac 12\sqrt n\log n$。不过常数小。

[ARC126C] Maximize GCD (*1824)

首先考虑 $\gcd_{x\in S} x\le \min_{x\in S}x$，当且仅当 $S$ 内元素全部相等时成立。于是如果可以使 $S$ 内元素全部相等答案即为最大可能的 $\min$。

否则最终 $\gcd a_i<\max a_i$。枚举这个 $\gcd$ 是什么，然后随便算一算即可。由于我没有脑子所以写了 $O(n\sqrt V)$。

[ARC126D] Pure Straight (*2332)

设 $dp_{i,S}$ 表示当前枚举到第 $i$ 位，已经选定的 $[1,m]$ 内的数的集合为 $S$，最小代价。转移考虑，如果不选这个数，则会移到所有选的数的前面或后面，贪心看哪个小选哪个。否则只用考虑 $S$ 内元素和它组成的逆序对即可。

[ARC126E] Infinite Operations $\color{blue}\Diamond$ (*2766)

非常有趣的脑电波题。

首先显然我们要会算一个序列的答案。这个操作很难直接模拟，$\color{blue}\Diamond$ 所以可以考虑设计一个势能函数 $f(a)$，把序列的变化转化成 $f(a)$ 的变化，从而求出操作次数。

而想要找到一个合适的势能，则可以考虑从结束状态入手。结束状态 $f(a)=0$，所有 $a_i$ 相同，也就是两两之间距离为 $0$。考虑令 $f(a)=\sum_{1\le i\le j\le n}|a_i-a_j|$。

先把 $a_i$ 排序。考虑对 $i,j(i<j)$ 操作一个 $\Delta$ 之后变成 $a'$，$f(a)$ 的变化。容易发现，$\forall k>j,a_k'-a_j'=a_k-a_j+\Delta,a_k'-a_i'=a_k-a_i-\Delta$，相抵消之后不变。而 $\forall k,i<k<j$，可以发现 $a_k-a_i+a_j-a_k=a_j-a_i=a_j'-a_i'-2\Delta$，对于 $a_j-a_i$ 则也是减少了 $2\Delta$。不难发现当且仅当 $j=i+1$ 时，势能减少的最少，为 $2\Delta$，也就是每次消耗 $2\Delta$ 的势能获得 $\Delta$ 的价值。

于是得到结论：答案为 $\frac 12\sum_{1\le i\le j\le n}a_j-a_i$。剩下的部分是 trivial 的，随便用一个线段树维护一下即可。重要的还是如何转化这个问题。

闲话：你这场 F 这么几把难是怎么评的 *3488 的啊？
哦，原来是某 2 Dan（指 rainboy）场了啊。
rainboy 害人不浅。

[ARC127C] Binary Strings (*2092)

考虑每一个位置选 $1/0$ 对排名的贡献。设当前数为 $x$，如果选 $0$，此数的排名为 $x$ 的排名 $+1$，否则，发现全部改为选 $0$ 的情况，排名都会在此数前面，则会将排名 $+2^{k+1}$，$k$ 为该位置为从低到高第几位。

所以，我们可以从高位开始枚举，每次能取 $1$ 就取，相当于每次将要求排名减去一个数。容易发现，如果取 $1$，要求排名对应位置一定也是 $1$，于是将那一位变为 $0$ 即可。否则，将排名 $-1$ 的操作相当于将一段为 $0$ 的后缀全部变成 $1$ 并将前一位变为 $0$。

这个操作很容易用线段树维护。直到排名的 $01$ 序列全为 $0$ 时停止。

[ARC127D] Sum of Min of Xor $\color{blue}\Diamond$ (*2593)

首先考虑计算 $(i,j)$ 为有序对时的答案，原问题答案只需要 $\times \frac 12$。先钦定 $\min(a_i\oplus a_j,b_i\oplus b_j)=a_i\oplus a_j$，$\sum a_i\oplus a_j$ 是容易拆位算的，于是考虑如何求 $\sum[a_i\oplus a_j>b_i\oplus b_j](b_i\oplus b_j-a_i\oplus a_j)$。

$>$ 并不好做，对于 $\oplus$ 常见的套路是枚举最高的不一样的位 $p$，设 $a_{i,j}$ 为 $a_i$ 的前 $j$ 位组成的数。则有 $a_{i,p-1}\oplus a_{j,p-1}=b_{i,p-1}\oplus b_{j,p-1}$。

$\color{blue}\Diamond$ 因为 $=$ 在 $\oplus$ 中有很好的性质，所以直接转化成 $a_{i,p-1}\oplus b_{i,p-1}=a_{j,p-1}\oplus b_{j,p-1}$，也就是 $a_i\oplus b_i$ 的一段前缀相等。把 $a_i\oplus b_i$ 全部丢到 trie 树上，则就是找到这段前缀对应的点，对于经过这个点后和 $a_i\oplus b_i$ 分开的 $a_j\oplus b_j$ 然后算贡献。这一部分是简单的，只用钦定 $a_i\oplus a_j=1$，预处理一些东西然后拆位算贡献即可。

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

[ARC127E] Priority Queue $\color{blue}\nabla$ (*2678)

怎么本质相同，思路完全不同的做法这么多。

考虑一个位置被删掉的数是 $x$，则显然 $\forall y>x$ 也是可行的。同时发现越往后的二操作能删的数的范围会越小，于是令删掉的数单调上升显然不劣。于是考虑删除集合，设 $dp_{i,j}$ 表示第 $i$ 个删除删除了 $j$ 的方案数。

每个 $i$ 都会有一个限制，具体地，考虑它要比前面所有删除操作和没有被删掉的数大，可以对于每个二操作删掉前面第一个一操作，剩下的就是上述的数，算出每个位置的限制即可。

[ARC128C] Max Dot (*1810)

首先，如果不考虑 $m$ 的限制，则有结论：$p_1$ 的极长相同连续段数量为 $2$，其中一段为 $0$。证明考虑不断拿出两个非 $0$ 段，设其平均值分别为 $x,y$，那么若 $x<y$ 则把前者的值全部给后者，否则把后者的部分给前者，使两段合并成一段最优。

有 $m$ 的限制则发现最多变成三段，具体是最后一段为 $m$，第一段 $0$。$O(n^2)$ 枚举即可。

[ARC128D] Neq Neq (*2554)

感觉还是套路题，不过后面想条件把自己绕晕了……

要求是选 $a_{i-1}\not=a_i,a_{i+1}\not=a_i$ 然后删 $a_i$，这很不好，套路地把删变成加，于是问题就变成，有多少个原序列的子序列，使得可以在其中进行若干次加数操作变成原序列。

容易发现这个子序列把原序列分成了若干个段，每个段之间独立，显然可以 dp。设 $dp_i$ 为子序列最后一位为 $i$ 时的方案数，现在只用快速找到能转移的范围即可。

先考虑如何判定一段 $[i,j]$ 能否合法。首先，如果中间有 $a_k=a_{k+1}$ 则显然不合法，并且若其中只有两种数，则什么操作都做不了，显然不合法。

最后结论是除了上面两种情况都合法。证明考虑类似归纳。随便选 $[i,j]$ 中值和 $a_i,a_j$ 中不同的一个位置 $k$，则若 $[i,k]$ 中只有两种不同，则可以在原来的 $[i,j]$ 中不断增加 $i$，否则归纳下去。

最后通过这些限制得到可以转移的范围，前缀和优化即可，有一些 $j-i\le2$ 的特判。

[ARC128E] K Different Values (*3049)

感觉好 sb 啊。怎么评到 *3000+ 的。

首先考虑如何判断一个局面是否有解。直觉上就是 $\max A_i\le \frac{\sum A_i}{m}+1$，且取等的不超过 $\sum A_i\bmod m$ 个。看了题解区知道可以归纳证明。

然后考虑最小化字典序，不难想到直接每一位判断当前是否需要放一个 $A_i=\frac{\sum A_i}{m}+1$ 的，然后找到最小的符合条件的 $i$ 即可。

[ARC129C] Multiple of 7 (*1687)

首先考虑 $777\cdots 7$ 这样长为 $x$ 的段，对答案有 $\frac{x\times(x+1)}2$ 的贡献，于是尝试用这种方法构造出来。考虑用若干个 $\frac{x_i\times(x_i+1)}2$ 得到出 $n$，每两段中间加入一个数隔开。

现在问题就变成了如何使得隔开的这几个数组成的数不能被 $7$ 整除。zlt 说随机，但是其实没有什么必要，因为打表发现最大的段数为 $m=6$，也就是可以直接爆搜。

但是这个方法太不漂亮了。考虑每次加入一段，决定中间的隔开的数。称这些数为 $b_1,\cdots,b_k$。考虑 $b_1,\cdots,b_k$ 分别到 $b_{k+1}$ 的子段组成的数，它们一定两两不同，否则前面一定有一段可以整除 $7$，并且没有 $0$。于是不妨先假设 $b_{k+1}=0$，和 $b_1,\cdots,b_k$ 组成的数分别为 $c_1,\cdots,c_k$，则 $c$ 中数互不相同。其中一定会有 $0$，此时再使 $b_{k+1}$ 变化，也就是使 $\forall i\le k,c_k\to (c_k+\Delta)\bmod 7$，使其中没有 $7$ 即可。

时间复杂度 $O(n+m^2)$。

[ARC129D] -1+2-1 $\color{blue}\Diamond$ (*2300)

原有的操作还是太难看了，考虑变化为前缀和。然后就会发现，操作变成了在前缀和数组 $s$ 上选一个位置 $i$，$s_i\to s_i-1,s_{i+1}\to s_i+1$。

但是发现一个问题：一个环的前缀和怎么定义？这是困难的，但是不妨换一个角度，$\color{blue}\Diamond$ 考虑 $a_i$ 是 $s_i$ 的差分数组，于是可以令 $s_i+a_i=s_{i\bmod n+1}$。这样当 $\sum a_i\not=0$ 时会出现矛盾，但是这个情况显然无解。

完成了 $s$ 的定义后就简单了。最后要还原成 $a_i=0$，变成 $s$ 则是 $s_i$ 全部相等。首先 $\sum s_i\bmod n>0$ 则无解，否则直接能操作就操作，直接模拟即可。具体地，只需要将整个环枚举两次即可。

[ARC129E] Yet Another Minimization $\color{blue}\Diamond$ (*3337)

非常有趣的网络流题！由于想到切糕那个 trick 所以成功自己独立做出来了。

首先看到题，发现题意是某些变量达成某种条件获得一定权值。结合非常小的数据范围，不难想到网络流。

然后想怎么建模。对于这种每个变量有若干取值的，想到切糕那题的方法。$\color{blue}\Diamond$ 具体就是，考虑对于每一个变量 $x_i$ 建出一条链，那么考虑最小割，链上一定要断掉一条边，断掉不同的边代表选不同的 $x_i=a_{i,j}$，代价为 $c_{i,j}$。

回到这道题，发现 $|x_i-x_j|$ 这一部分难以处理。考虑进行一些转化。容易发现 $|x_i-x_j|=\sum_{x_i\le k\le x_j}1+\sum_{x_j\le k\le x_i}1$。

考虑每条链上都建值域个点，然后 $\forall i\not=j,\forall k$，链 $i$ 的第 $k$ 个点向链 $j$ 的第 $k$ 个点连一条流量为 $W_{i,j}$ 的边。不难发现，此时如果取 $x_i=x,x_j=y$，则还需要割的边有 $|x-y|$ 条，满足要求。

但是这样建图离散化之后也有 $O(n^2m)$ 个点，$O(n^3m)$ 条边，会被精心构造数据卡掉。

但是可以发现，上面链 $i,j$ 之间的连边，有很多都是多余的。于是考虑不建多余的点，考虑对于链 $i,j$，$i$ 向 $j$ 怎么连边。

从小往大扫 $a_{i,k}$ 和 $a_{j,k}$，记录一个量 $lst=a_{j,1}$。对于一个 $a_{i,k}$，依次枚举所有还没枚举过的，满足 $a_{j,l}<a_{i,k}$ 的 $l$，则 $(i,k)$ 向 $(j,l)$ 连流量为 $W_{i,j}\times(a_{j,l}-lst)$ 的边，然后 $lst\to a_{j,l}$。

枚举完后，再让 $(i,k)$ 向 $(j,p+1)$ 连流量为 $W_{i,j}\times(a_{i,k}-lst)$ 的边，其中 $p$ 为这次枚举到的 $\max l$，然后 $lst\to a_{i,k}$。

如果我给你解释为什么这样连是对的可能要解释很久，所以不如自己手玩一下理解吧。

这样点数 $O(nm)$，边数 $O(n^2m)$，复杂度用 dinic 是 $O(n^4m^3)$，足以通过。

[ARC130D] Zigzag Tree $\color{blue}\nabla$ (*2437)

考虑令黑点为相邻点全部大于它的，白色反之。则这棵树一定是黑白相邻的。

然后考虑 dp。设 $dp_{u,i,0/1}$ 表示在 $u$ 子树内，点 $u$ 的排名为 $i$ 的方案数。转移时考虑 $v$ 中有多少排名在 $u$ 前面，乘上几个组合数，并前缀和优化即可。

[ARC130E] Increasing Minimum $\color{blue}\Diamond\Box$ (*3188)

非常厉害的题！一直想到差分约束状物去了，$\color{blue}\Diamond\Box$ 但是事实上差分约束并不适合做这种要求最小化字典序的题，还是要从整体上去分析整个序列的性质。

考虑对操作序列分段，每一段操作完后 $\min$ 不变。考虑如何分段是合法的。首先每一段内不能有重复的数。其次后面的段中的数的集合是完全包含前面的。这是因为第 $i-1$ 段操作完后，段内所有出现过的数都变成了 $\min +1$，在下一段也一定会操作，以此类推。不难发现这两个条件加起来就是充要的。

然后就可以 dp 了。设 $dp_i$ 表示前 $i$ 位最少分多少段。贪心地，考虑最后一段 $[p,i]$ 时，$p$ 越小越好。找到最小的合法的 $p$ 转移即可。

此外，最后一段不一定要满足上述第二个条件。最后枚举倒数第二段的结尾位置，找到 $dp_i$ 最小，其次 $i$ 最大的。这样使得每个位置都取到了能取到的最小值，自然也最小化了字典序。

最后得到所有数的最终值，倒过来模拟一边即可。$O(n)$ 的！太厉害了。

[ARC130F] Replace by Average $\color{blue}\Diamond$ (*3211)

又独立切铜牌题了！

首先有一个显然的结论：如果操作可以使某个 $a_i$ 变小，则进行操作一定不劣，原因显然。

然后，经过大力手玩和瞪眼观察可以发现一个非常厉害的结论：最终的序列是下凸的。考虑如果不是，一定 $\exists i,a_i-a_{i-1}\ge a_{i+1}-a_i$ 即 $a_i\ge \frac{a_{i-1}+a_{i+1}}2$，操作完后一定不劣。$\color{blue}\Diamond$ 类似这样 $\frac{a_i+a_j}2$ 或者有类似关系的都可以尝试从凸性去分析，以及在考虑一个序列的整体时可以尝试考虑凸性。

再然后，还有一个很显然但是至关重要的结论：如果固定 $[l,r]$，只在 $[l,r]$ 内选 $i,j$ 进行操作的话，差分数组 $b_i=a_i-a_{i-1}$ 的 $\sum_{l<i\le r}b_i$ 是不变的。原因也显然，因为和就等于 $a_r-a_l$。

有了这些结论就可以开始做了。考虑每次加入一个 $a_i$，序列如何变化。因为每次增量可以看作是先把前面能操作的做了，再加入，符合性质一，于是是正确的。显然可以通过若干次调整使序列满足条件，但是时间复杂度不能接受。

这时发现下凸等价于 $b_i\le b_{i+1}$，也就是说，加入 $a_k$ 时，只要调整使得 $b$ 仍然单调不降即可。

考虑如果 $b$ 被影响的区间为 $[j,k]$，那么这一段的 $b$ 会如何变化。首先根据上面的结论三，它们的和不变。于是不难得到一个结论：这一段的 $b_i$ 都会近似变成 $\frac{\sum_{j\le i\le k}b_i}{k-j+1}$。证明可以考虑放在坐标系上，大致就是变成一条线段。当然具体地，可能分成两段，后面一段的值为前面一段的 $+1$。

剩下的就简单了，考虑用单调栈维护值相同的段，每次 pop 出所有会被影响的段，修改 $b$ 的值之后再加进去。时间复杂度 $O(n)$。

[ARC131C] Zero XOR $\color{blue}\triangle$ (*1162)

会不了一点！会不了一点！会不了一点！会不了一点！会不了一点！会不了一点！会不了一点！会不了一点！会不了一点！会不了一点！会不了一点！

结论：如果 $n\bmod 2=1$ 则先手必胜，否则若一步能获胜则先手胜，否则后手胜。

证明：令当前全部数异或和为 $s$，则若先手操作 $x$ 后，后手可以操作 $y$ 一步获胜，则 $x\oplus y=s$，注意到数列中的数两两不同，即这样的 $x,y$ 最劣情况下两两配对。由于 $n\bmod 2=1$，一定有一个数没有配对，后手再操作一个数，则变成了 $n-2$ 的情况。

[ARC131D] AtArcher (*2271)

考虑先把每个区间一定造成的贡献算上，若区间可能造成多一次的贡献，则考虑第一个 $>0$ 的位置，对应的位置一定是一段区间。差分维护。其次还要分讨左右两边放多少个，总之就是分讨就完了。。。

[ARC131E] Christmas Wreath (*2314)

考虑没有异色三连星（？）等价于有每个环有两条同色边，钦定这两条边都和其中编号最大的相连，则要求变成每个点和所有小于它的点相连的边都同色。暴力背包 $O(n^5)$ 能过？

为什么是对的？首先 $n\le 4$ 或 $n\bmod 3=2$ 的时候无解，否则考虑一个 $O(n)$ 做法。发现 $n=6,7,9,10$ 时可以玩出解，$n>10$ 时找到对应的 $n-6$ 的情况构造即可。所以所有又解情况都可以用这种方式构造。真是蠢完了/qd

[ARC131F] ARC Stamp $\color{blue}\Diamond\Box$ (*3501)

还是很有趣的吧？

首先考虑操作等价于选择一个 ARC 并将这三个位置变为通配符，则来的这三个位置一定只能是 ARC，AR*，A**，**C，*RC，*R* 中的一种。$\color{blue}\Diamond\Box$ 考虑将原串分割成上面的串或者分隔符的形式，然后考虑 dp。

思考：为什么不直接在原串上 dp？

感觉可能也可以，但是涉及到的状态很多，分讨起来很麻烦，似乎类似构建一个自动机？

考虑如何 dp，由于分段是形如 (A/AR)ARC(C/RC) 或者是 ...CRA... 的形状，这其中除了 ARC 都要求其他的某些位置已经被操作，所以考虑设 $dp_{i,j,0/1}$ 表示当前枚举到 $i$，已经用了 $j$ 次操作，是否钦定下一段一定选。

考虑如何去重，其实就是一个简单的原则：不进行无用操作。显然如果操作完后和原串一样则可能是无用的，但是要考虑到，比如 ARARCC 中的 AR 或 C，这两段都要求中间的 ARC 要操作，则此时 ARC 就算操作完还一样也是有意义的。于是对于每一段判断这段是否可以操作完不变，乘上转移系数即可。

[ARC132C] Almost Sorted $\color{blue}\nabla$ (*1616)

经典题，之前还给学弟讲了一次。注意到 $d$ 很小，所以 $p_i$ 的可能值只有 $2d+1$ 种，并且还是一个以 $i$ 为中心的区间，于是考虑动态地状压记录这个区间内哪些数已经被选过然后转移即可。

[ARC132D] Between Two Binary Strings (*2221)

首先相邻相同的位置最多等价于连续段数量最少。先思考怎样的一个序列是合法的，考虑每一个 $1$，知道了它的起点终点，则这个 $1$ 在这段区间中就是合法的。

那就将问题转化为了，每个 $1$ 有一个限制 $[l_i,r_i]$ 将 $1$ 分成若干个段，使得每段都 $\exists j,\forall k,l_k\le j+k-1\le r_k$。还是不好处理，于是令 $l_i\to l_i-i,r_i\to r_i-i$，则变成了这一段中区间交集不为空。注意到这个东西有单调性，于是直接双指针，再随便用个数据结构维护区间 $\max l_i$ 和 $\min r_i$ 即可。

[ARC132E] Paw $\color{blue}\Diamond\triangle$ (*3144)

逆天诈骗题，应该多想一会儿的。

$\color{blue}\Diamond\triangle$ 考虑最终状态，发现一定形如 <<<<<*******>>>>>，中间一段没有被操作过。于是可以对每两个洞之间的段统计有多少种方案中，这一段不会被操作。不难发现这只和左/右洞的数量有关。

设 $dp_i$ 表示有 $i$ 个洞，且操作不影响到右边的概率。转移考虑第一次操作，若第一次操作就影响了，则这一次操作一定是操作最右边的洞，且向右走。概率为 $\frac 1{2i}$。然后可以将操作的洞和段删掉，变成 $i-1$ 的子问题。于是 $dp_i=\frac1{2i}dp_{i-1}$。最后枚举段统计答案即可。

[ARC132F] Takahashi The Strongest $\color{blue}\Diamond\triangle$ (*3076)

很 educational 的题，做完之后对 FWT 有了更深的理解。

首先考虑 C 是绝对赢家当且仅当 AB 出的一样，并且 C 出的可以获胜。那么第一步就是要求出 AB 每一轮出的是否相同/出的是什么的每种情况的方案数。但是如果直接枚举复杂度会到 $O(9^k)$。

但是注意到这个求方案数的问题相当于求 $c_i=\sum_{j\otimes k=i}a_jb_k$，其中 $\otimes$ 是某种运算，整体上是卷积形式。$\color{blue}\Diamond$ 具体地，我们将每轮的决策压成四进制形式，定义 $x\otimes y=\begin{cases}x&x=y\wedge x,y\not=3\\3&x\not=y\end{cases}$ ，该运算是对 $x,y$ 的每个四进制位分别做。然后进行 FWT，具体地，我们构造 $fwt(a)_i=\sum_{j\otimes i=i}a_j$，由于 $(i\otimes j)\otimes(i\otimes k)=i\otimes(j\otimes k)$ 所以是可行的，然后 FWT 和 IFWT 都是简单的。

现在已经知道 AB 每种决策会出现的情况数了，然后就要求 C 每种决策的合法情况数。（如果我没想错的话）应该是可以直接容斥的。$\color{blue}\Diamond$ 但是还有一个很巧妙的方法：逐位处理。其实本质上和 FWT 相同，就是每次将当前位从原来 AB 的决策数变成 C 的决策数。把存在一轮是绝对赢家变成没有一轮是，然后通过一个 dp 就可以简单解决。最后复杂度是 $O(4^kk)$。

---

这里插播一道题。

CF2031D Penchick and Desert Rabbit $\color{blue}\Diamond$

一个经典结论：对于这样逆序对/顺序对间连边的东西，一个联通块是一个连续段。证明考虑若 $i,j$ 之间有边，则 $(i,j)$ 中数一定会和 $i,j$ 中至少一个有边。于是找出每个连续段再算最大值即可。

为什么又是见过的 trick 不会？红温了。

---

[ARC133C] Row Column Sums (*1583)

先判无解，然后考虑从全 $k-1$ 改，设每行每列分别要减掉的值为 $c_i,d_i$，则最少要减掉的就是 $\max\sum c_i,\sum d_i$。这显然是答案的上界，构造证明考虑不妨设 $\sum c_i<\sum d_i$。则先把 $\sum c_i$ 全部填完，并且在超过 $d$ 的条件。而剩下 $\sum d_i-\sum c_i$ 则可以全部放在一行里，将每个 $d$ 补充完。由于优解，所以这个值一定是 $k$ 的倍数，从而不会影响 $c$。

[ARC133D] Range XOR (*2658)

首先 $\bigoplus_{l\le i\le r} i=V$ 的条件很难处理，考虑差分，记 $f_n=\bigoplus_{i\le n} i$，则变成 $f_{l-1}\oplus f_r=V$。而根据经典结论，求单个 $f_i$ 是简单的，具体地，$f_i=\begin{cases}i&i\bmod 4=0\\1&i\bmod 4=1\\i+1&i\bmod 4=2\\0&i\bmod 4=3\end{cases}$。

所以先把 $l=L$ 和 $r=R$ 的情况判掉，要求的就是 $\sum_{L\le i<j\le R}[f_i\oplus f_j=V]$。再分成两部分：$i,j$ 中有 $\bmod 2=1$ 的情况和没有的。有的情况，考虑算出来 $[L,R]$ 内 $0/1$ 的数量再判断 $[L,R]$ 内是否有 $V/V\oplus 1$。

对于没有的情况，发现限制相当于选这个范围中两个数 $\bmod 4=0/3$ 的数 $x,y$，$x\oplus y=V$ 的情况数。于是直接考虑去掉最后一位，$L,R,V$ 相应调整，问题就变成了 $\sum_{L'\le i<j\le R'}[i\oplus j=V']$。直接数位 dp 即可。

[ARC133E] Cyclic Medians $\color{blue}\Diamond\Box$(*3238)

非常好题。考虑一般和中位数相关的问题，我们的做法都是，令中位数为 $k$，则让 $>k$ 的为 $1$，$\le k$ 的为 $0$，然后变成 $01$ 序列上的问题。$\color{blue}\Diamond\Box$ 对于计数问题也是类似的，考虑 $x=\sum_{i\ge 0}[x>i]$，于是可以枚举 $0\le k\le V$，将 $>k$ 的变成 $1$，$\le k$ 的为 $0$，对于每个 $k$ 算答案，加起来就是真正的答案。

此时就考虑如何算答案。由于是 $01$ 序列，所以 $x$ 和 $y,z$ 取中位数时，如果 $y=z$ 则变成 $y$，否则还是 $x$ 不变。于是如果序列里出现了 $(0,0)$ 或 $(1,1)$，最终值就和初始值无关了，只跟最后一次出现的这样的对有关。

但是直接对这个计数是困难的，$\color{blue}\Diamond$ 于是考虑一些性质，由于是 $01$ 序列相关的计数，考虑 $0,1$ 某种程度上是对称的，具体地，设最后一次出现的相同对是 $(0,0)/(1,1)$ 的情况数是 $f(k,0/1)$，则 $f(k,0)=f(V-k,1)$，也就是说，每个最后是 $(0,0)$ 的序列都和某个最后是 $(1,1)$ 的序列一一对应。所以，我们只需要求出不存在相同对的方案数，存在的答案就是 $\frac{(k+1)V^{n+m}}2$！

现在就只用求序列中不存在相同对的情况数。考虑将 $(x,y)$ 对中的 $y\to y\oplus 1$，也就是变成了 $x,y$ 序列完全相同，并且同时有长为 $n,m$ 的循环节。所以序列一定有长为 $g=\gcd(n,m)$ 的循环节。对于循环节的每一位，若 $x=0,y=1$ 则方案数为 $k^{\frac ng}(V-k)^{\frac mg}$，否则为 $k^{\frac mg}(V-k)^{\frac ng}$，所以总的方案数为 $(k^{\frac ng}(V-k)^{\frac mg}+k^{\frac mg}(V-k)^{\frac ng})^g$。

[ARC134C] The Majority (*1560)

先把除了 $1$ 之外的填好，那么每个非 $1$ 的都要对应一个 $1$，剩下的 $1$ 随便填即可。

[ARC134D] Concatenate Subsequences (*1998)

先考虑在 $[1,n]$ 中的部分，这部分中的元素显然单调不降，否则把降的部分删掉更优。记 $f_i=\min_{j\ge i}a_j$然后分类讨论：

• 若 $\exists i,a_i=f_1\wedge a_i\ge a_{i+n}$，那么只留一个 $a_i$ 和可行的最小的 $a_{i+n}$ 即可。
• 否则不断加入 $a_i=f_i$ 的数，令第一个选的 $a_{i+n}=x$，分类讨论：
• • 若 $a_i>x$，显然不优，直接结束。
  • 否则若 $a_i<x$，直接加入。
  • 否则 $a_i=x$，那么考虑加入的第一个 $\not=x$ 的 $a_{i+n}$ 和 $x$ 的大小关系，判断是否加入即可。

[ARC134E] Modulo Nim $\color{blue}\nabla$ (*3026)

考虑先分析简单的情况。设数的集合为 $S$。则：

• 若 $|S|=1$，则 $\{1\},\{2\}$ 显然必败，否则考虑 $x\bmod (x-1)=1$，必胜。
• 若 $\exists x\in S,x\bmod 2=1$，选 $\bmod 2$，必胜。同理当 $\exists x\in S,x\bmod 4=2$ 时必胜。
• 否则若 $\bmod 3$ 后 $S=\{1\},\{2\}$ 则必胜。
• 否则 $\bmod 12$ 后，$S=\{4,8\}$。$\{4,8\}$ 可以玩出来是必败，则原来不为 $\{4,8\}$ 的情况必胜。

剩下 $\forall x\in S，12\mid x$ 的情况，发现这样的 $x$ 最多只有 $16$ 个，直接状压，记录当前 $S$ 中有哪些 $12|x$ 的 $x$，边界情况为 $\exists x\in S,12\not\mid x$ 的情况。

[ARC135C] XOR to All $\color{blue}\nabla$ (*1512)

不难发现操作两次及以上一定不优，于是枚举操作哪一个拆位算贡献即可。

[ARC135D] Add to Square $\color{blue}\Diamond\Box$ (*2750)

其实就差了中间一个挺妙的转化，最后结论都大致猜到了（

考虑将 $(i+j)\bmod 2=1$ 的 $(i,j)$ 位置上的元素 $\times(-1)$，答案不变的同时，容易发现操作不会影响每行每列的和。于是令第 $i$ 行的和为 $f_i$，第 $i$ 列的和为 $g_i$，则答案有一个显然的下界为 $\max(\sum |f_i|,\sum |g_i|)$。

同时还有一个很重要的观察：$\color{blue}\Diamond\Box$此时，若两个矩阵的 $f_i,g_i$ 全部相同，则一定可以互相转化。证明考虑可以操作使得左上 $(n-1)\times (m-1)$ 的矩阵全部为 $0$，剩下的元素是固定的，于是可以通过这个中间状态变成所有状态。

考虑答案是否能取到这个下界。不妨令其为 $\sum|f_i|$。则要求就是第 $i$ 行的所有数和 $f_i$ 同号。若 $\exists i,j,f_i>0,g_j>0$，则令 $a_{i,j}=\min(f_i,g_j)$，同理当 $f_i<0,g_j<0$ 的时候一样。

进行完这些操作后 $g_i$ 一定全部 $=0$，剩下的 $f_i$ 之和也一定为 $0$（因为 $\sum f_i=\sum g_i$）。于是随便找一列，每次找一个 $f_i>0,f_j<0$，将其中绝对值较小那个消成 $0$ 即可。

[ARC135E] Sequence of Multiples $\color{blue}\nabla$ (*3157)

细节不太想重新理解了，大概就是，观察到不同的 $\frac{a_i}i-\frac{a_{i-1}}{i-1}$ 只有 $O(\sqrt[3]X)$ 个，然后类似整除分块，找到每一段然后算。

[ARC135F] Delete 1, 4, 7, ... $\color{blue}\Diamond\Box$ (*3821)

太牛了，尝试不看题解再把式子推一遍。

首先不难发现当 $k$ 比较大的时候最后的 $n_k$ 很小，具体当 $k=40,n_0=10^{14}$ 时，$n_k<10^7$。于是考虑是否可以求出每个位置上的元素。设进行 $k$ 次操作后的 $a_i$ 为 $f_k(i)$，可以得到 $f_k(i)=f_{k-1}(\left\lfloor\frac{3i+1}2\right\rfloor)$。于是可以 $O(kn(\frac23)^k)$ 解决。

否则 $k<40$。$\color{blue}\Box$ 尝试打表可以发现，$f_k(i+2^k)=f_k(i)+3^k$。证明考虑归纳。首先 $k=0$ 显然正确。然后

$f_k(i+2^k)\\ =f_{k-1}(\left\lfloor\frac{3i+1}2\right\rfloor+3\times 2^{k-1})\\ =f_{k-1}(\left\lfloor\frac{3i+1}2\right\rfloor)+3^k\\ =f_k(i)+3^k$

$\color{blue}\Diamond$ 这是一个非常厉害的性质，由于 $2^k$ 的存在可以做很多类似倍增的操作。

此时已经有一个 $O(k2^k)$ 的做法了：由于知道 $f_k(i)$ 就能知道 $f_k(i+2^k)$，考虑枚举 $i\in[0,2^k)$ 算 $f_k(i)$ 就能等比数列求和得到 $\sum f_k(i)$。

但是还不够，由于 $k\le 40$，联想到折半，考虑设 $x=\left\lfloor\frac k2\right\rfloor,y=\left\lceil\frac k2\right\rceil$，则要求的就是 $\sum f_y(f_x(i))$。

$\sum_{i=1}^{n_k}f_y(f_x(i))\\ =\sum_{i=0}^{2^x-1}\sum_{j=0}^{\left\lfloor\frac{n_k}{2^x}\right\rfloor}f_y(f_x(i+j2^x))\\ =\sum_{i=0}^{2^x-1}\sum_{j=0}^{\left\lfloor\frac{n_k}{2^x}\right\rfloor}f_y(f_x(i)+j3^x)$

然后设 $F(a,b)=\sum\limits_{i=0}^{a}f_y(b+i3^x)$，则以原式 $=\sum\limits_{i=0}^{2^x-1}F(\left\lfloor\frac{n_k}{2^x}\right\rfloor,f_x(i))$。考虑类似倍增，拆成若干个 $[s,s+2^t-1]$ 的区间，则有

$\sum_{i=s}^{s+2^t-1}f_y(a+i3^x)\\ =\sum_{i=0}^{2^t-1}f_y(a+(i+s)3^x)\\ =\sum_{i=0}^{2^t-1}f_y(a+s3^x+i3^x)$

则设 $g(a,b)=\sum\limits_{i=0}^{2^a-1}f_y(b+i3^x)$，则只需要求出所有的 $g(a,b)$ 即可。但是注意到 $b$ 可能很大，所以再简化一点。设 $u=b\bmod 2^x,v=\left\lfloor\frac b{2^x}\right\rfloor$。则

$g(a,b)\\ =\sum_{i=0}^{2^a-1}f_y(u+2^xv+i3^x)\\ =\sum_{i=0}^{2^a-1}f_y(u+i3^x)+3^xv\\ =2^a3^xv+\sum_{i=0}^{2^a-1}f_y(u+i3^x)$

这样就有 $u<2^x$ 了，于是 $g(a,b)$ 的状态数就是 $O(2^{\frac k2}\log n)$ 的了。

然后就考虑求 $g(a,b)$。还是类似倍增的，考虑从 $g(a-1,*)$ 转移过来：

$g(a,b)\\ =\sum_{i=0}^{2^a-1}f_y(b+i3^x)\\ =\sum_{i=0}^{2^{a-1}-1}f_y(b+i3^x)+\sum_{i=0}^{2^{a-1}-1}f_y(b+(i+2^{a-1})3^x)\\ =\sum_{i=0}^{2^{a-1}-1}f_y(b+i3^x)+\sum_{i=0}^{2^{a-1}-1}f_y(b+2^{a-1}3^x+i3^x)\\ =g(a-1,b)+g(a-1,b+2^{a-1}3^x)$

于是设 $B=40$，复杂度 $O(kn(\frac23)^k+2^{\frac B2}(B+\log n))$，做完了。

推式子成功了

[ARC136C] Circular Addition (*2137)

首先区间加不难联想到差分。于是设 $b_i=a_{i \bmod n+1}-a_i$，则每次操作形如选 $b_i\leftarrow b_i-1,b_j\leftarrow b_j+1$。则有个下界为 $\sum[b_i>0]b_i$。还有另一个显然的下界为 $\max a_i$。

接下来证明答案就是这两个下界取 $\max$。若前者更大，则每次选随便一个 $b_i>0,b_j<0$。否则，若 $a_i$ 全部相同，则整个操作，否则一定能找到 $a_{i-1}<a_i,a_{j+1}<a_j$。操作即可。

[ARC136D] Without Carry $\color{blue}\nabla$ (*1908)

直接高维前缀和，记 $f_{a,b,c,d,e,g}$ 为每一位分别 $\le a,b,c,d,e,g$ 的数量，随便预处理一下就行。

[ARC136E] Non-coprime DAG (*3100)

很有趣的小清新题！

首先既然要求反链，那么就肯定要关心一个问题：如何判断 $i$ 能否到达 $j(i<j)$？

若 $i,j$ 均为偶数，显然 $i,j$ 间就有边。否则，考虑 $i$ 为奇数，那么考虑 $i$ 的一条出边能到达的点 $u$，记 $i$ 的最小质因数为 $f_i$，则显然有 $\min u=i+f_i$。对于 $j$ 的入边，入点为 $v$ 时也是一样，$\max v=i-f_i$。

同时发现，这样的 $v$ 一定是偶数，原因显然。也就是说，若此时 $u\le v$，则 $i$ 一定可以到达 $j$。于是设 $L_i=\begin{cases}i-f_i&i\bmod 2=1\\i&i\bmod 2=0\end{cases},R_i=\begin{cases}i+f_i&i\bmod 2=1\\i&i\bmod 2=0\end{cases}$。则 $i$ 可以到达 $j$ 当且仅当 $R_i\le L_j$。再把 $L_i,R_i$ 看作若干个区间 $[L_i,R_i)$，则一个点集 $S$ 构成反链当且仅当 $S$ 中的区间交集不为空。

当然你会发现这个 $[L_i,R_i)$ 在 $i\bmod 2=0$ 的时候有问题，不过事实上你不能同时选两个这样的 $i$，于是后面特判一下。

这个问题是简单的，考虑枚举这些区间的交一定包含 $[i,i+1)$ 这段区间，问题就变成了有多少区间包含 $[i,i+1)$，差分即可。还有可能要选 $i\bmod 2=0$ 的 $i$，则此时区间的交一定包含 $i$ 这个点，也是统计有多少包含点 $i$ 的区间即可。

最后 $1$ 一定是能选的，加上即可。$O(n)$ 解决。

[ARC137C] Distinct Numbers $\color{blue}\Diamond$ (*2043)

看讨论区叫 决策包含性 的东西确实很厉害啊！

结论：若 $a_n-a_{n-1}>1$ 则一定先手必胜。考虑 $a_n\leftarrow a_n-1$ 的状态，被当前状态完全包含。

$\color{blue}\Diamond$ Lemma：若有状态 $A$ 能一步到达 $B$ 且完全包含 $B$，则 $A$ 一定必胜。证明考虑，若 $B$ 必败则 $A$ 显然必胜。否则 $B$ 一定有个后继必败，$A$ 能到达这个后继，必胜。

否则考虑 $a_n-a_{n-1}=1$，此时双方都不会操作变成 $>$ 的状态，于是每次操作一定有 $a_n=a_{n-1}+1$，则每次使最大值 $-1$，判断奇偶性即可。

[ARC137D] Prefix XORs $\color{blue}\Diamond\nabla$ (*2191)

考虑计算 $a_n$ 的值，对每个值 $a_i$ 分开算贡献。$\color{blue}\Diamond$ 可以发现 $a_n'=\sum a_{n-i}\binom{k+i-1}i$。证明考虑把 $(n,k)$ 看作坐标，则 $a_{n-i}$ 的贡献相当于在网格图上从 $(n-i,1)$ 走到 $(n,k)$ 的方案数。因为 $s_i=\sum_{j\le i} a_j$ 可以看作从 $(j,y-1)$ 先往下一步，再往右走到 $(i,y)$。

然后考虑异或，则当且仅当 $\binom{k+i-1}i\bmod 2=1$ 时有贡献。

$\color{blue}\Diamond$ Lemma：$\binom nm\bmod 2=1$ 当且仅当用二进制表示成集合时 $m\subseteq n$。证明考虑 Lucas 定理：$\binom nm=\binom{n\&1}{m\&1}\times\binom{\left\lfloor\frac n2\right\rfloor}{\left\lfloor\frac m2\right\rfloor}$，其实也就是拆位，每位做。所以要求就是每位都有 $\binom nm=1$，不难发现当且仅当 $(n,m)=(0,0),(1,0),(1,1)$ 时成立，即 $m\subseteq n$。

所以 $\binom{k+i-1}i\bmod 2=1$ 当且仅当 $(k-1)\&i=0$。可以暴力对于每个 $k-1$ 枚举子集的补集 $O(3^{\log n})$，也可以高维前缀和 $O(n\log n)$。

[ARC137E] Bakery $\color{blue}\Diamond\Box$ (*3034)

首先这个题面看着就很网络流。考虑建模。$\color{blue}\Diamond\Box$ 正向算每天的收益比较困难，考虑先算总收益，再减去最少需要减去的。

然后考虑一个类似志愿者招募的建模：$\color{blue}\Diamond\Box$ 我们连一条 $1\to n+1$ 的链，每个 $i\to i+1$ 连 $(a_i,D),(lim-a_i,0)$ 两条边。经过这条边表示不制作面包。而如果你制作的面包少于 $a_i$ 个了，则每少制作一个面包就会减少 $D$ 的收益。

除此之外还有 $l_i\to r_i+1$ 的 $(1,c_i)$ 的边，表示选了第 $i$ 个面包师并制作面包。由于这会让 $[l_i,r_i]$ 内的 $j\to j+1$ 的边都少 $1$ 的流量，所以相当于制作了面包。

然后使用 Atcoder library 的网络流库通过。