A 加减

求k次前缀和，转化为$a_{x}a\_x$ 加1 , $a_{y}a\_y$ 减1，若和模m非0则无解，对求完前缀和的数组排序，找到一个分界点，分界点前减到0，分界点后加到m，加和减的总和相同，答案为加的总和。时间复杂度O(nk+nlogn)

B Austin Love Math

由题意知 $f(x)=\frac{x}{\sqrt{x^2+1}}f(x)\; =\; \backslash frac\{x\}\{\backslash sqrt\{x^2\; +1\}\}$ 则

$f_1(x)=f[f(x)]=\frac{\frac{x}{\sqrt{x^2+1}}}{\sqrt{\frac{x^2}{x^2+1}+1}}=\frac{x}{\sqrt{2x^2+1}}f\_1(x)\; =\; f[f(x)]\; =\; \backslash frac\{\backslash frac\{x\}\{\backslash sqrt\{x^2\; +1\}\}\}\{\backslash sqrt\{\backslash frac\{x^2\}\{x^2\; +1\}\; +\; 1\}\}\; =\; \backslash frac\{x\}\{\backslash sqrt\{2x^2\; +1\}\}$

$f_2(x)=f[f_1(x)]=\frac{\frac{x}{\sqrt{2x^2+1}}}{\sqrt{\frac{x^2}{2x^2+1}+1}}=\frac{x}{\sqrt{3x^2+1}}f\_2(x)\; =\; f[f\_1(x)]\; =\; \backslash frac\{\backslash frac\{x\}\{\backslash sqrt\{2x^2\; +1\}\}\}\{\backslash sqrt\{\backslash frac\{x^2\}\{2x^2\; +1\}\; +\; 1\}\}\; =\; \backslash frac\{x\}\{\backslash sqrt\{3x^2\; +1\}\}$

由数学归纳法得到通式 $f_t(x)=\frac{x}{\sqrt{(t+1)x^2+1}}f\_t(x)\; =\; \backslash frac\{x\}\{\backslash sqrt\{(t+1)x^2\; +1\}\}$

C 牛哥与AI

数据范围是1000以内，标程是$O(n^2)O(n^2)$的，但是没有刻意卡$O(n^{2}logn)O(n^2logn)$的做法。

我们可以$O(n^2)O(n^2)$枚举左右位置，然后对两个位置进行转换、左删右增、左增右删这几种操作。

可以考虑哈希加set对01串进行处理，对于每个01区间我们都要进行哈希，虽然有许多重复，但是依然很容易造成哈希冲突，可以使用双哈希等进行优化，然后再在set中删除那些只进行一次甚至更少次数转换就能得到的字串，常数写得小的情况是能通过该题的。

我们这里还是来讨论一下造成重复的串是哪些：

首先，我们把连续的一段1或者0称为一个游程。

1.对于转换操作，其实很容易得出存在$C_n^{2}C\_n^2$种选择方式

2.对于增删操作，由于删除和增加操作会造成长度的删减，因此一定是一个删除操作和一个增加操作，先假设删除位置为i，在增加位置为j的后面()，那么这个操作就相当于选择一个区间删除头部后全部左移然后在尾部添加数字。

我们可以发现以下性质：

删除游程中的一个数字和删除游程开头的一个数字影响是一样的，因此我们枚举删除的区间可以一段一段地枚举。

在游程中增加一个相同的数字和增加在其末尾或开头影响是一样的，因此我们添加的数字只需要保证和前面那个数字相异

假设我们选中的区间只有两个游程，例如000111，那么增删之后就会变为001110，可以发现只相当于转换了两个位置，因此我们枚举的区间游程要大于2，并且只要游程是大于2的区间，就必定能产生一个新的01串

但是这样还是比答案大一些，如果区间是类似于010101这种每个游程只有一个数字的区间，那么左删右增和左增右删获得的串是一样的，这就是被我们统计重复的串，需要删除。

D Alex的诅咒

idea来自于三角刨分求多边形面积这个知识点，首先可以证明得到，如果需要满足题目要求，那么选点都应该再凸包上，所以我们需要先求凸包，然后在凸包上进行选择，具体选择方法使用DP，我们将前一个点以及总共选取点数封装成一个状态进行DP转移，注意需要枚举所有第一个点进行DP，为了避免计算几何烦人的精度问题，选择了输出凸包面积的两倍这个技巧。

E 序列变换

操作结束最后每个数是原始数组若干个数的异或和，可以计算判断原始数组能有多少种不同的子集异或和判断是否有解：可以将所有数插入线性基，设 $kk$ 为线性基里的元素的个数，则有 $2^{k}2^k$ 种不同的子集异或和，若 $2^k\ge n2^k\; \backslash ge\; n$ 则有解。主体思路是先用原数组构造出线性基，然后构造出子集异或和前 $nn$ 小。可以用不超过 $30^{2}30^2$ 次操作构造一个行简化阶梯形矩阵，实际上只用成功插入 $\lceil {}_{2}n\rceil \{\backslash lceil\backslash log\_2n\backslash rceil\}$ 个元素即可停止，因此可用不超过 ${\lceil {}_{2}n\rceil }^2\{\backslash lceil\backslash log\_2n\backslash rceil\}^2$ 次操作构造出能生成至少 $nn$ 个数的基。然后可以用这个基构造第k小，具体方法：可用3次操作交换一对数，把构造出来的基移动到2的幂次方的位置上，然后其他位置可用一次操作清零，2次操作递推构造出第k小。总操作次数比${\lceil {}_{2}n\rceil }^2+3n\{\backslash lceil\backslash log\_2n\backslash rceil\}^2+3n$ 略少，时间复杂度O(n*30)。

F 魔王大人的打工日常

容易知道，交换相邻两个碟子，逆序对奇偶性变化，一次循环右移相当于最后面的元素交换r-l次，所以奇偶性变换只和交换区间长度r-l+1的奇偶性和循环右移次数k有关，当k为奇数，r-l为奇数时，逆序对偶性变化。

G Ring Fit Adventure

为了方便，考虑行从第0行开始，但列仍然是从第1列开始。单独考虑第0行对于答案列的贡献,可以发现 $f[0][j]f[0][j]$ 对 $f[i][m]f[i][m]$ 的贡献次数是 $\left(\genfrac{}{}{0px}{}{i}{m-j}\right)\backslash binom\{i\}\{m-j\}$.解释如下

• 思路1:对答案列贡献次数就是从(0,j)到(i,m)每次只能向下或向右下走，路径的数量,总共有i步，需要向右下走m-j步,即 $\left(\genfrac{}{}{0px}{}{i}{m-j}\right)\backslash binom\{i\}\{m-j\}$.

• 思路2:观察给定的递推式，发现是异或形式的杨辉三角递推式，也可以得出同样的结论。

由于要求的是xor,只需要关心贡献次数奇偶性,即 $\left(\genfrac{}{}{0px}{}{i}{m-j}\right)\mathrm{m}\mathrm{o}\mathrm{d}2\backslash binom\{i\}\{m-j\}\; \backslash mod\; 2$。

由Lucas定理可知,$\left(\genfrac{}{}{0px}{}{i}{m-j}\right)\mathrm{m}\mathrm{o}\mathrm{d}2=\left(\genfrac{}{}{0px}{}{i\mathrm{m}\mathrm{o}\mathrm{d}2}{(m-j)\mathrm{m}\mathrm{o}\mathrm{d}2}\right)\times \left(\genfrac{}{}{0px}{}{\lfloor \frac{i}{2}\rfloor }{\lfloor \frac{m-j}{2}\rfloor }\right)\mathrm{m}\mathrm{o}\mathrm{d}2\backslash binom\{i\}\{m-j\}\; \backslash mod\; 2=\backslash binom\{i\; \backslash mod\; 2\}\{(m-j)\; \backslash mod\; 2\}\; \backslash times\; \backslash binom\{\backslash lfloor\backslash frac\{i\}\{2\}\backslash rfloor\; \}\{\backslash lfloor\backslash frac\{m-j\}\{2\}\backslash rfloor\}\; \backslash mod\; 2$，考虑第一个组合数乘数，当括号下面不超过上方才为1。

所以,第一行某元素j对第i个答案的贡献次数为奇当且仅当m-j在二进制下是i的子集.

于是问题转化为了将第一行下标反转,给定集合价值,求1-n子集异或合的问题.即sos-dp问题. 直接枚举子集和使用容斥复杂度都不符合要求.

我们设 $dp[mask][i]dp[mask][i]$ 代表 $maskmask$ 子集种只有右边 $ii$ 位(下标从0开始）不同的集合状态，上述问题中即子集异或和。那么我们根据第i位的状态不同，转移方程不同，具体如下：

当第i位为0时，显然子集集合没有改变 $dp[mask][i]=dp[mask][i-1]dp[mask][i]=dp[mask][i-1]$

当第i位为1时，$dp[mask][i]=dp[mask][i-1]\oplus dp[mask\oplus 2^i][i-1]dp[mask][i]=dp[mask][i-1]\; \backslash oplus\; dp[mask\; \backslash oplus\; 2^i][i-1]$

即可使用$O(d\ast 2^d)O(d*2^d)$的复杂度解决这个问题，其中d是二进数位数。

H 合成大西瓜

$\mathbf{\text{当一个等级高的球在一个等级低的球之上的话，等级低的球就没用了，所以可以忽略掉}}\backslash textbf\; \{当一个等级高的球在一个等级低的球之上的话，等级低的球就没用了，所以可以忽略掉\}$

所以虽然给的n很大，看似状态很多，但其实只有$\mathbf{\text{8种}}\backslash textbf\; \{8种\}$

设：

f(0)表示现在没有球，为了达到胜利仍需操作的期望次数

f(1)表示现在有1个一级球，为了达到胜利仍需操作的期望次数

...

f(321)表示现在从下往上依次是三级球、二级球、一级球，为了达到胜利仍需操作的期望次数

然后可以列出以下方程组：

稍微解释第一个式子，这个式子就是一开始是没有球的，因为会平均概率的放进一个一、二或三级球，所以有1/3的机会进入f(1)状态，有1/3的机会进入f(2)状态，有1/3的机会进入f(3)状态，最后的加1是代表当前操作一次...后面的式子同理

通过高斯消元可以求出每一种状态的解，所以只需要求出初始序列是以上8种中的哪一种，输出对应答案即可。

I 这是一个签到题哦

略

J 修棋盘

手玩可知，从起点出发，不管如何走，到达同一个点的步数的奇偶性是不变的，切走到第 $ii$ 行第 $jj$ 列的步数一定与 $i+ji+j$ 的奇偶性一致。所以不存在 $-1-1$ 的情况。先判断初始棋盘是否合法，若合法输出0，否则输出不满足 $a[i][j]==(i+j)\mathrm{m}\mathrm{o}\mathrm{d}2a[i][j]\; ==\; (i\; +\; j)\; \backslash mod\; 2$ 的格子数量即可。