队名为寄
A
By Margarita
本题的关键在于构造出\(1\)位置中最小数于最左边 以及\(0\)位置中最大的数在最右边，只有在给定串中，这两个数才是\(10\)。后将两个数排除对其他位置冒泡排序，再将两个数移动到\(01\)交界处使得给定串变为形如\(0\cdots101\cdots1\)的样式，而又由于其他串这两个位置均不能产生\(10\)，故其他串均排序。
B
By Nerovix
给一个凸包，在凸包上找三个点，满足：这三个点构成的三角形的反互补三角形完全覆盖此凸包。如果ΔABC三遍中点分别为X,Y,Z，则称ΔABC是ΔXYZ的反互补三角形。凸包1e6个点。
如果固定三个点中的两个，不难发现第三个点至少必须满足：它到两固定点所在直线距离最大。因此，定下两个点，第三个点就定了。因此实际上只有两个动点。跑这两个点的双指针就行了。
C
By Margarita
本题对于一个点\(i\)考虑，若\(a_i<k\)我们仍将\(a_i\)减去\(k\)，此时\(a_i<0\)，若一直减则该点的贡献为\(\text{减的次数}-\lceil-\frac{a_i}{k}\rceil\)。该式子为一个分段的结构，考虑加操作，若加的数足够进入上一阶段，则原数也进入上一阶段，我们发现原数与该数具有某种阶段等价性，只有减数的时候才能改变两者阶段的差值，故点\(i\)对答案的贡献就是\(\text{减的次数}-\text{阶段差值}\)。我们又发现每次到达一个新的阶段差值的时候，原数必然\(<k\)，我们只需关系当时的阶段差值即可，即为\(\lceil-\frac{\min a_i}{k}\rceil\)，我们只需维护历史最小值，可以用\(\text{Sengment Tree Beats}\)解决。
D
By J_B_Y
不妨假设\(n\leq m\)，有结论当且仅当\(1\times1\)时先手败，其他时候都先手胜。
分情况证明，当\(1\times m\ (m\geq2)\)时，先手直接取到剩\(1\times 1\)，后手败。
当\(2\times m \ (m\geq2)\)时，先手不断维护第一行比第二行少一个的形状即可获胜。
当\(n\times m\ (n,m\geq3)\)时，先手直接取得只剩最后一行和一列，然后可以证明先手必胜。
E
By J_B_Y
令\(g_u(x)\)为\(u\)为根子树\(b_u=x\)时的最小值，\(f_u(x)=\min_{y\geq x}g_u(y)\)，那么有转移\(g_u(x) =(x-a_u)^2+ \sum f_v(x)\)。
要求\(g_u(x)\)的最值，不妨尝试求导得到\(g_u'(x) = 2(x-a_u)+\sum f_v'(x)\)
由\(f_u(x)=\min_{y\geq x}g_u(y)\)，容易得到\(f_u'(x) = \max\{g_u'(x), 0\}\)。
用\(S_u \subset \R\times \N\)，表示\(f_u'(x)\)的拐点，利用上述转移可以证明\(f_u'(x)=\sum_{(i,\delta)\in S_u}\delta ReLU(x - i)\)。
并且有\(S_u' = \cup S_v, S_u = \{(i,\delta)\in S_u'\ | \ i<x_0 \} \cup \{(x_0, g''(x_0^+))\}\)，其中\(x_0\)为\(g_u'(x) = 2(x-a_u)+\sum f_v'(x)\)的零点。
记\(C_u\)为\(f_u(x), g_u(x)\)的最小值，带入转移式可得
\[ C_u = (x_0 - a_u)^2 + \sum C_v + \sum \int_{-\infty}^{x_0} f'_v(x) \]
用启发式合并合并即可
F
G
By Margarita
\(k=0\)的时候答案显然为\(1\)，特判即可。
考虑\(k\)次前树的形态是长成什么样的。
- 对于右跳边\((u,r_u)\)，由于其仍是向右的边，故在\(k\)次操作前\(r_u\)的父亲是\(u\)的\(k\)级祖先，记为\(fa^k(u)\)，即边为\((fa^k(u),r_u)\)，若\(u\)没有\(k\)级祖先则给定树形态不合法，答案为\(0\)
- 对于左跳边\((u,l_u)\)，我们可以钦定其往上跳了几次，即原来的边为\(i\in[0,k],(fa^i(u),l_u)\)
观察发现右跳边是强制的，右跳边之间的左跳边是有调整空间的，并且右跳边将左跳边很好地分割开来，所以每一段左跳边都是独立的，我们只需要将他们的贡献简单乘起来就好，一段左跳边的贡献显然只与其长度有关，考虑长度为\(i\)的一段的贡献。
我们将一段左跳边抽象成一个长度为\(i\)的线段，我们将钦定节点\(r\)的父亲的行为变为在这个线段上画一个\((l,r)\)的线段，由于我们最多往上跳\(k\)次，故有\(r-k\le l\le r-1\)，由于初始状态是\((r-1,r)\)，故我们只画出改变初始状态的线段，故\(r-k\le l\le r-2\)，记\(f_i\)为长度为\(i\)的线段的贡献，我们可以得到转移式子\(f_i=f_{i-1}+\sum_{j=2}^{\min\{k+1,i\}}f_{j-2}*f_{i-j}\)，意义显然。
考虑用生成函数加快求\(f\)的速度，记\(g=\sum_if_ix^i\)
- 当\(i\le k+1\)时，有\(g=1+xg+x^2g^2\)，解得\(g=(1-x-\sqrt{1-2x-3x^2})/2x^2\)，取求出的\(g\)中前\(k+2\)项为\(g'\)
- 当\(i>k+1\)时，有\(g=1+xg+x^2g*g'\)，解得\(g=1/(1-x-x^2g')\)，截取前\(n+1\)项即可
使用多项式求逆即可求出\(g\)，需要注意的是由于\(x^2\)不能直接求逆，故需要进行适当展开。
之后\(\text{dfs}\)下去得到每条左跳链的长度即可求出答案。
I
高端的数学题。
我们可以发现题目中的\(\text{rand}\)函数可以表示为一个\(k\times k\)的矩阵\(A\)，对向量\(x\)调用\(\text{rand}\)函数实际上就是\(x\rightarrow Ax\)。那么题目就变成了对每个\(x\)求最小的\(r\)使得\(A^rx=x\)，即为\((A^r-E)x=0\)，我们发现满足该式子的\(x\)个数是\(A^r-E\)的零空间大小，即为\(|\ker(A^r-E)|=2^{k-rank(A^r-E)}\)，但是零空间内包含了所有周期\(r'|r\)的向量\(x\)，故我们还需要进行一次容斥，具体地令\(f_r\)为以\(r\)为周期的\(x\)个数，\(g_r\)为以\(r\)为最小周期的\(x\)个数，有\(f_r=\sum_{r'|r}g_{r'}\)故做一次莫比乌斯反演或直接枚举容斥即可求出\(g_r\)，最终答案就为\(\sum_r r*g_r\)。
但是我们还不知道哪些\(r\)是有效的，我们还需要对\(r\)的性质进一步讨论。由群论的拉格朗日定理或者打表可知，所有有效的\(r'\)都是\(A^r=E\)的解\(r\)的因子，那么我们只需要求解\(A^r=E\)即可，这个可以用\(\text{BSGS}\)解出，又由打表或者高端的数学证明可知\(r<2^k\)，故\(\text{BSGS}\)的时间复杂度是对的。
综上所述，总的时间复杂度为\(O(nk^2+k^2\sqrt{2^k}+d_r^2)\)，可以勉强通过此题。
实际上我们还可以用矩阵\(A\)的极小多项式将时间复杂度变为\(O(nk^2+k^3+k\sqrt{2^k}+d_r^2)\)，但是我不会，就这样吧。
L
By Margarita
手玩一下发现每\(3\)个周期后，\((x,y,z)\rightarrow \left((a\circ b\circ c)_x,(b\circ c\circ a)_y,(c\circ a\circ b)_z\right)\)则预处理出三个轮换环及\(0,1,2\)轮开始的经过的数字，注意到\(a,b,c\)均为排列，故环中无重复数字，则问题变为了解同余方程组，使用\(\text{CRT}\)即可。
M
By J_B_Y
显然任意时刻能凑到的水一定是\((x,y)\)即\(Ax+ By\)的形式
判断可行性可使用\(Ax + By = C\)的判定，即\((A,B)\ | \ C\)，考虑一组解的最小步数。
有显然当\(x, y \geq 0\)能构造出\(2(x+y)\)的方案，其中一者小于零时有\(2(\lvert x\rvert + \lvert y\rvert) - 1\)的方案。并且通过构造势能函数能够证明这是最小步数的方案。
那么只需要找到最靠近零的周边的几种方案计算最小答案即可