ARC136 A-E
A A ↔ BB
贪心。可以把 BB 换成 A，可以把 BA 换成 AB。
B Triple Shift
直观上觉得只要数集相同，那么就是可以变换的。大概方法就是每次找到正确的数把它挪到数列的端点，这样显然是可行的。但是在相反的三个上出现了问题，原因在于只剩最后两个数时方向可能是反着的。分析发现每次移动改变两对数的相对位置，那么逆序对奇偶性应该不变，判断一下即可。如果存在相同的数发现是不用判断奇偶性的，一定存在合法的方案。
C Circular Addition
显然差分，环上问题就在环上差分，得到一个数列。感官上和正负有关，而正负值之和为零，而每次操作都能让一个地方加一另一个地方减一，猜想答案是差分数组中正数的和。操作中需要保证数不小于零，每次挑极长正数即可，有效消耗了差分数组。然后解决掉剩下的部分就可以了，表现出来就是正数的和与数列中最大值取 max 输出即可。具体操作方法是考虑两个量（差分值和最大值）的消耗情况。如果后者大，那么发现不存在为 \(0\) 的元素，全局减就能消耗一个后面值；如果前面大，那么找到一个最大值连续段就能消耗前者；如果一样大，说明至少没有浪费的，刨掉山谷就能得到一个双赢的方案。于是就正确了。
D Without Carry
高维前缀和。写起来非常不优雅。
E Non-coprime DAG
思考两个数什么时候会建立联系。首先两个偶数本身就有边，然后考虑奇数和偶数。令 \(x\) 为最小的奇数的质因子，那么奇数要到达最近的偶数必须要加上或者减去这个数。奇数和奇数也是一样的，发现通过奇因子不如偶因子实在，所以条件仍然如前面所说的。于是乎每个奇数就有了一个区间，一个数不想被ban就只能让自己的区间和这个区间有交，把每个数的区间找出来差分找最大值即可，可以做到线性。
ARC137 A-E
A Coprime Pair
直觉上答案会出现在区间的边际上，暴力枚举一些即可。证明不会。
B Count 1's
找最大子段和与最小子段和即可，线性。
C Distinct Numbers
需要用到一个技巧，即决策包容性。是说如果一个状态可以到达一个子状态（一个就够了）的所有子状态，那么这个状态就是必胜态。证明上考虑对这个子状态分类讨论，如果是必输那么状态必赢，如果必赢那么存在子状态必输，那么状态仍然是必赢的。考虑这个问题，如果最大值和次大值没有靠拢，那么最大值减一就是那个子状态，显然这个状态的所有子状态都可以由原状态转移过来，所以就是必胜的。至于相邻的情况，由于先手不能让后手有机会，只能让后面的数连续，决策是唯一的，求一下决策数判奇偶即可。
D Prefix XORs
学到了两个技巧。首先就是对数列 \(a\) 做 \(k\) 次题目所述的前缀和，那么应该有：
\[a^k_n=\sum\limits_{i=0}^{n-1}\binom{i+k-1}{k-1}a^1_{n-i} \]具体含义就是考虑贡献的路径计数，总共需要跳 \(k\) 步，于是就有上面那个式子。也就是说如果上面那个组合数是奇数那么对答案就有贡献，否则没有。此时需要另一个技巧，即用卢卡斯来拆分组合数。
\[\binom{i+k-1}{i}\%2=\prod\limits_t\binom{(i+k-1)_t}{i_t}\%2 \]要得到 \(1\) 必须满足不出现 \(\binom{0}{1}\)。也就是说 \(i+k-1\) 应该包含 \(i\)。如果前者存在进位，那么肯定会破坏某个位置上的 \(1\)，所以 \(k-1\subseteq\complement_ui\)。做一次高维后缀和即可。
E Bakery
好东西。有两种思考方式。
一种是考虑让面包进行流转。首先假如我们已经获得了 \(114514\) 块面包，但事实上我们并没有这些面包，于是我们就需要付出一些代价。代价分为三种，一种是取消掉免费面包的订单，一种是取消付费面包的订单，一种是花费一些代价雇佣面包师来做这些面包，希望最小化三者的和。表现在模型上就是连 \((i-1,i,0)\)，\((i-1,i,d_i)\)，\((l_i-1,r_i,c_i)\)，限定一下流量（本来就只借了这么点面包啊）跑最小费用最大流即可。
另一种是正着考虑。想着往最小费用循环流上靠拢。考虑连 $(i,i+1,0/-d_i) $ 表示得到的钱的相反数，然后连 \((r_i+1,l_i,c_i)\) 表示雇佣的钱的相反数，求最小费用循环流。而最小费用循环流的方法大概就是将每一条负边变成三条边，一条反边和两条连向源汇点的边，删删减减和上面的模型是相同的。然而感觉并没有上面那种方法直观。
ARC138 A-E
A Larger Score
交换两个数最少的操作次数应该是距离，所以枚举每个前面的数找最近的更小的数即可。
B 01 Generation
模拟。
C Rotate and Play Game
猜想可以取到最大的一半数。令最大的一半数是 \(1\)，小的是 \(-1\)，画出折线图，从最高点开始新建起点一定能保证没有冒头的点，即符合题意。
D Differ by K bits
考虑差分，那么差分出来的数应该是一堆满足 \(\text{cnt=k}\) 的数，而这些数应该是要构成所有的这些数的。那么考虑把它们都丢进线性基，如果能丢满说明有解，构造上线性基中得到了 \(k\) 个上述的基底，参照格雷码把这些基底组合起来即可。
E Decreasing Subsequence
感觉很巧妙的题目。
首先将数列转化成图的形式，具体而言是对于所有 \(a_i>0\) 的点连边 \((i,a_i-1)\)。观察这张图，发现每个点都有至多一个出度和一个入度，并且一定是从后往前连边，也就是说每张图应该都是一个链的集合。进一步观察发现这些链的划分和原数列是双射关系，而由于链的连边是有顺序的，所以链的划分等价于把原集合划分成一些不相交的集合，这对后面的计数有帮助。
观察合法序列对应的图，发现选出来的数对应了 \(2k\) 个点，记为 \(p_1,p_2\dots p_{2k}\)，发现它们要求回文地连边，并且边和边之间是包含的关系。考虑以最中心的那条边为基准把这 \(k\) 条链上的点划分成前后两个部分，两个部分都是 \(k\) 条链，将链尾和链首拼起来就是一组合法的方案（我们要求的那 \(k\) 条边就是那 \(k\) 对链首和链尾的连边）。
于是就有了柿子：
\[\text{ans}=\sum\limits_{i,j}\binom{n+1}{i+j} \begin{Bmatrix}i\\k\end{Bmatrix} \begin{Bmatrix}j\\k\end{Bmatrix} \sum\limits_{t} \begin{Bmatrix}n+1-i-j\\t\end{Bmatrix} \]我声称有了上面的解释这个柿子会非常容易理解，有一个点是说由于建出来的图包含 \(0\) 号点，所以柿子中是 \(n+1\)。后面那堆显然是可以优化的，复杂度 \(O(n^2)\)。
标签：arc136,arc137,那么,奇数,题解,差分,即可,Bmatrix,状态 From： https://www.cnblogs.com/Feyn/p/17637136.html