记 $p_i=\frac{i(n-i+1)}{\binom{n+1}{2}}$，即一次操作中 $i$ 被选中的概率，设 $h_{i,j}$ 表示经过 $j$ 次修改（不一定包含 $i$）后 $a_i$ 的期望，则 $h_{i,j}=\sum_k{g_k\binom{j}{k}p_i^k(1-p_i)^{j-k}}$，展开用二项式定理化简得 $h_{i,j}=\frac{m-1}{2}(1-(1-\frac{p_i}{2})^j)$，记 $P_i=1-\frac{p_i}2$，则 $h_{i,j}=\frac{m-1}{2}(1-P_i^j)$。

最后加入查询操作，设 $c_{i,j}$ 表示经过 $j$ 次操作（不一定包含 $i$）后 $a_i$ 的期望，则 $c_{i,j}=\sum_{k=0}^j\binom{k}{j}(\frac{2m}{2m+1})^k(\frac{1}{2m+1})^{j-k}h_{i,k}$，同样展开并把 $(1-P_i^k)$ 拆开并对两部分分别使用二项式定理收拢，得 $c_{i,j}=\frac{m-1}{2}(1-(\frac{2mP_i+1}{2m+1})^j)$，记 $R_i=\frac{2mP_i+1}{2m+1}$，则 $c_{i,j}=\frac{m-1}{2}(1-R_i^j)$。

最后求答案，枚举 $i$ 并枚举查询操作的位置 $j$ 计算贡献，有 $E(a_i)=p_i·\frac{1}{2m+1}\sum_{j=1}^q c_{i,j-1}$，展开后后半部分是 $(q-\sum_{j=0}^{q-1}R_i^j)$，容易等比数列求和，于是 $E(a_i)=\frac{p_i}{2m+1}\frac{m-1}{2}(q-\frac{R_i^q-1}{R_i-1})$，答案即为 $(\binom{n+1}{2}(2m+1))^q\sum E(a_i)$。

设计一个 dp，$f_i$ 表示前 $i$ 个字符能得到多少种不同的串，发现一个 $T$ 可以由多个分段方式得到，于是我们钦定 $T$ 的每个分割点均尽可能考前，也就是如果某一个字符对应的段中末尾一段的异或和为 $0$，则钦定其放入下一段，则如果给定 $T$，我们可以得到一个贪心构造方案：从 $S$ 开头开始，选取最短合法段作为 $T$ 的当前字符，直到 $T$ 中每个字符都对应某段且 $S$ 中没被匹配的后缀异或和为 $0$。一种特殊情况是 $S$ 仅由一种字符组成，特判掉。

那么我们只需要对于每个 $i$ 以及值 $1\leq x\leq 3$，找到其后面第一个 $j$ 满足 $(i,j]$ 合成 $x$ 即可。这一步的预处理是平凡的。$O(|\sum|n)$。

手玩很困难，无解的判断暂时搁置，先挖掘一下性质：值为 0 的点是特殊的，操作它无效；值为 1 的点可以换到任何位置；……

操作位置跟着某个值走看起来不是很有前途，因为很多值都不能经过每个位置，考虑不停操作同一个位置：假设 $p_i=x$，若 $x=0$，怎么操作也没用；否则操作一次之后 $x$ 就会去往位置 $(i+x)\bmod n$，如果 $x$ 回到了 $p_i$，那么需要操作 $i$ 时 $p_i=x$，但此时 $x$ 不在位置 $i$ 上，于是除 0 外一个值不会出现第二次。也就是不断操作一个位置，这个位置上的值会遍历若干不重复的值之后到 0 停止。

一个直观的想法是利用这个性质直接做，但是发现在这个过程中会混乱地影响其他位置的值。我们需要找到一个顺序使得后面的不会影响前面的。假设先令 $p_0=0$，为了不让 $p_0$ 被交换，需要让所有 $i+j\equiv 0+0\pmod n$ 的组都让 $j$ 作为 $p_i$ 的终态，即操作到这个状态就必须停止，否则前面的就会被打乱。那么这步操作之后得到的序列就是 $\{0,n-1,n-2,\cdots ,1\}$，现在的图实际是一个以 0 为中心的菊花，但我不是很会构造这种特殊情况怎么排序，操作一番之后可以得到 $\{n-1,n-2,\cdots ,1,0\}$。

一种直接构造 $\{n-1,n-2,\cdots,1,0\}$ 的方案是，观察到第一种构造的本质是钦定一个 $x=0$，使得所有 $i+p_i$ 都同余 $x$。那么这种构造中的 $x=n-1$，于是从 0 所在的位置开始，向前推就可以做到降序。

对于这种情况我们可以对它的后缀依次排序：对于位置 $i$，假定 $[i+1,n)$ 已经有序（$p_{i+1}=0,p_{i+2}=1\cdots$）之后插入 $p_i$ 只需要对 $i$ 连续操作 $n-1-i$ 次。于是发现任意排列都能规到这种状态下，不存在无解。

const int N=1e6+10;
int n,p[N];vector<int> g;
void work(int i){g.push_back(i),swap(p[i],p[(i+p[i])%n]);}
signed main(){
    n=read();For(i,0,n-1)p[i]=read();
    Rof(i,n-1,0)while(p[i]!=n-1-i)work(i);
    Rof(i,n-2,0)For(j,1,n-1-i)work(i);
    cout<<g.size()<<endl;for(auto v:g)printf("%d\n",v);
    return 0;
}

代码非常好写。

大多题解是讲得不那么清楚的找规律。提供一种不带脑子分类讨论的做法。

首先把一个 L 形的位置定义为其对应的 $1\times 1$ 的正方形左下角格点坐标，其中正方形有两条相邻的边是 L 形的部分，那么一个正方形就有 $4$ 种 L 的形态。先观察性质：把使得 L 位置改变的操作当做一组，一次改变会向四个方向之一移动一步，可以得到，假设这次移动穿过了正方形的某条边，则若这条边是原 L 的边，花费是 $1$，否则花费是 $2$；然后新的 L 形的其中一条边在穿过的这条边上，另一条边只需要相邻。并且在交替走上/下和左/右时，后一步的花费是 $1$。

讨论目标位置的 $x,y$ 均 $\ge 0$ 的情况：一定每一步都是向右或向上，第一步由于正方形的右方和上方都没有边，所以代价一定是 $2$，此后尽可能用代价为 $1$ 的移动，最后一段再走代价为 $2$ 的。也就是先交替向右向上，最后一段一直大力向一个方向走。于是走到目标格子的花费就是 $x+y+\max\{1,|x-y|\}$，和 $1$ 取 $\max$ 是因为第一步一定需要花费 $2$。走到目标格子时候形态还不一定对得上。不妨考虑最后一步若向右，且目标正方形的左边有 L 的边，或最后一步向上，且目标正方形的下方有 L 的边，则不需要额外调整，否则还需要 $1$ 的代价来调整。

然后是 $x\ge 0,y<0$ 的情况。注意到 $x<0,y\ge 0$ 的情况与其是对称的，于是只用处理一种。类似地，第一步我们一定是向下走一步，接下来转成 $x\ge 0,y\ge 0$ 但初始 L 形有翻转的情况。此时和上面唯一的不同是，第一步的花费不一定是 $2$ 了。类似稍微讨论一下可以得到新的贡献。

最后是 $x<0,y<0$ 的情况，与上面类似，归到 $x\ge0,y\ge0$ 的情况之后也只需要讨论一下第一步是怎么走的就好了。$O(T)$。

过程中不会出现 $x\cdots y\cdots x$ 的棋子分布，可以归纳证明：在只有 $len\le2$ 时显然满足，则棋子分布有 $01,10,0,1$ 四种类型，后两种类型操作后显然还在这四种之内，一二种等价，不妨讨论一下：$101\to 111,001,011,010\to 000$，则 $len+1$ 时依然满足。

考虑对于一种 $c$，若 $c_1 = c_n$，则最后答案固定，对于每个 $s$ 贡献都是 $2^{n-2}n$，否则是 $c_1\not = c_n$ 的情况，不妨设$c_1=0,c_n=1$，另一种情况是完全等价的。

边界的点是特殊的，因为无论如何它的颜色都不会改变。设这个局面为 $111\dots X\dots000$，$X=c_{l\cdots r}$，另一种对称的情况类似。

若 $X$ 不存在，即局面为 $a$ 个 1 接着 $b$ 个 0，则对于任意 $s$ 均贡献 $\sum_{a=1}^{n-1}a$。

否则 $X$ 存在且 $1<l<r<n,c_l=0,c_r=1$。若先到达 $[1,l)$，则贡献为 $r$；若先到达 $(r,n]$，则贡献为 $l-1$。

考虑对于一个 $l<r$，它贡献的情况：对于 $s-(l-1)<(r+1)-s$，即 $s<\frac{l+r}{2}$，贡献为 $R=2^{r-l-1}r$，否则贡献为 $L=2^{r-l-1}(l-1)$。由于对称的出现，实际贡献为 $2^{r-l-1}(L+R)$；特殊地，当 $s-l=r-s$ 时，贡献应修正为 $2^{r-l-1}(R+R)$，也就是额外在这个位置加上 $2^{r-l-1}(R-L)$。

第一部分的贡献容易处理，枚举 $x=r-l-1$ 并解出 $l,r$ 的范围再全局贡献；第二部分的贡献则需要枚举 $s$，也是容易计算的。复杂度 $O(n+\log p)$。

设 $a_0=0,a_{n+1}=n+1$，初始选中 $0,n+1$，不影响计算答案。

假设第一步 $[1,n]$ 里选了 $a_x$，则接下来问题分裂为了两个子问题 $[1,x),(x,n]$，第二步选择是不会对没有影响到的那个区间产生贡献的，这启发我们以区间作为状态进行 dp：设 $f_{l,r}$ 表示在 $[l,r]$ 区间中，$a_l,a_r$ 已经被选择，$a_{l+1\cdots r-1}$ 都还没被选择时，区间内期望选中多少个数。转移只需要枚举区间中合法的下一步 $a_{b_{1\cdots k}}$ 满足 $l<b_i<r,a_l<a_{b_i}<a_r$，转移则可以假设我们只关注这个区间时，所有选择没在区间里的数的操作都忽略，否则选择到每个 $b_i$ 是等概率的，那么转移就显然有 $f_{l,r}=1+\frac{1}{k}(\sum_{i=1}^k (f_{l,b_i}+f_{b_i,r}))$，最终答案为 $f_{0,n+1}$。特殊地，若 $k=0$ 则 $f_{l,r}=0$。至此得到了 $O(n^3)$ 的做法。

接下来我们把计算 $k$，$\sum f_{l,b_i}$，$\sum f_{b_i,r}$ 三部分分别处理。$k$ 用二维前缀和处理；$\sum f_{l,b_i}$ 要求 $l<b_i,a_l<a_{b_i}<a_r$，前两个小于在 $f$ 的状态设计里天然满足，于是仅要求 $a_{b_i}$ 的值在一个区间，后面一个同理，维护两类树状数组。$O(n^2\log n)$。

套路地拉出直径 $(s,t)$，设其长度为 $len$。把 $s$ 的颜色固定为黑色，最终答案乘二。若 $t$ 的颜色也是黑色贡献显然为 $len\times 2^{n-2}$，否则 $s,t$ 不同色。

一个关于直径的结论是，树上离某个点最远的点之一一定在任意一条直径端点中。考虑与一个非直径端点 $u$ 的最远同色点，设其为 $v$，若 $v$ 不是直径端点且选 $v$ 严格优于选同色直径端点，则 $v$ 到那个同色直径端点更优于 $(u,v)$。至此我们得到，$\max(X,Y)$ 一定等于某个非直径端点到对应同色直径端点的距离。于是每个非端点携带一个二元组属性 $(x,y)$ 表示到两个端点的距离，则可以从每个二元组中选择一个出来，再取它们的 $\max$ 就是权值。

这样我们就可以进行计算了，记 $f_x$ 表示选择的最大值 $\ge x$ 的方案数，则这部分的答案等于 $\sum_{x\ge 1} f_x$。$f_x$ 的计算依赖于 $n-2$ 个点的三种状态：$x,y$ 均 $<x$，个数记为 $A$；$x,y$ 恰有一个 $<x$，个数记为 $B$；$x,y$ 均 $\ge x$，个数记为 $C$。则当 $C>0$ 时，$f_x=2^{n-2}$，否则 $f_x=2^A(2^B-1)$。

预处理 $2^k$ 可以做到线性。

打表发现当 $\min(i,j)>4$ 时有 $a_{i,j}=a_{i-1,j-1}$，尝试解释这个现象，不妨对于一个左上角 $(i,j)$ 进行一些讨论。注意，要求它能够影响它右方以及下方的元素，即 $i,j>1$；此外当讨论涉及到 $i-1$ 行，$j-1$ 列时，要求其是自然生成而非给定的，即 $i,j>2$。

• $a_{i,j}=0\Rightarrow a_{i+1,j}>0,a_{i,j+1}>0\Rightarrow a_{i+1,j+1}=0$，即 $0$ 在任意位置都具有向右下的传递性；
• 综合，当 $a_{i,j}=0$ 是，情况为一步之后始终为 $0$。

• $a_{i,j}=1\Rightarrow a_{i+1,j},a_{i,j+1}=0/2$：

  • 当两者均为 $0$ 时，推出 $a_{i+1,j+1}=1$，且 $0$ 会跟着传递，故 $a_{i+k,j+k}=1$；
  • 当两者均为 $2$ 时，推出 $a_{i+1,j+1}=0$，故会在这里产生一次不同，之后依赖于 $0$ 的传递性。
  • 当恰有一者为 $0$ 时，设 $a_{i,j+1}=0,a_{i+1,j}=2$，有 $a_{i+1,j+1}=1$，$a_{i+1,j+2}=0$。此外，由于 $a_{i+1,j}$ 是自然推出，则 $a_{i+1,j-1}=0$，传递性会保证 $a_{i+2,j}=0$，则由 $(i+2,j),(i+1,j+1)$ 可以推出 $a_{i+2,j+1}=2$，配合 $a_{i+1,j+2}=0$，变为了 $(i+1,j+1)$ 的相同子问题，故 $1$ 在这种情况下拥有传递性。
• 综合，当 $a_{i,j}=1$ 时，情况分为一步之后始终为 $0$ 与一步之后始终为 $1$。

• $a_{i,j}=2\Rightarrow a_{i+1,j},a_{i,j+1}=0/1$：

  • 当两者均为 $0$ 时，推出 $a_{i+1,j+1}=1$，且 $0$ 会跟着传递，故会在这里产生一次不同，之后依赖于 $1$ 的传递性。
  • 当两者均为 $1$ 时，推出 $a_{i+1,j+1}=0$，之后依赖于 $0$ 的传递性。
  • 当恰有一者为 $0$ 时，设 $a_{i,j+1}=0,a_{i+1,j}=1$，有 $a_{i+1,j+1}=2$，$a_{i+1,j+2}=0$。此外，由于 $a_{i+1,j}$ 是自然推出，则 $a_{i+1,j-1}=0$，传递性会保证 $a_{i+2,j}=0$，则由 $(i+2,j),(i+1,j+1)$ 可以推出 $a_{i+2,j+1}=1$，配合 $a_{i+1,j+2}=0$，变为了 $(i+1,j+1)$ 的相同子问题，故 $2$ 在这种情况下拥有传递性。
• 综合，当 $a_{i,j}=2$ 时，情况分为一步之后始终为 $0$，一步之后始终为 $1$，与一步之后始终为 $2$。

当 $a_{i,j}=1/2$ 时，均有一种情况依赖于前一行一列，故当 $i,j>2$ 时，最长不完全传递的情况为 $2\to 1\to 0$。所以当 $i,j>4$ 时，一定有 $a_{i,j}=a_{i-1,j-1}$。事实上通过随机数据也能发现对于 $\min\{i,j\}\leq 4$ 均可能不满足该性质。

不知道怎么做的最优化题目想想网络流。$|x|=\max\{x,-x\}$，放进这题就是同一个连通块的 $B_i$ 要同时选择权重 $1$ 或 $-1$。那么每个点的选择有：删除（贡献 $-A_i$），不删除（贡献 $B_i$ 或 $-B_i$）。

拆点 $u$ 为 $u_1,u_2$，连边 $S\to u_1\to u_2\to T$，割掉三条边的意义设为 $+1$ 权，删除和 $-1$ 权，然后运行最小割模型，也就是初始答案为 $\sum |B_i|$，然后减去最小割，容易根据 $B_u$ 的正负性确定边权。

考虑“连通块”的限制，即对于一条边的两端点若都没被删除，则必须选择同一种权值。考虑选不同权值的情况：存在边 $(u,v)$，满足存在边 $u_1\to u_2,v_1\to v_2$，且 $S\to u_1,v_2\to T$ 或 $S\to v_2,u_1\to T$，为了让这种情况不出现，只需要 $u_2\to v_1$，$v_2\to u_1$ 并把边权设置为 $\infty$。

最终点数为 $2n+2$，边数为 $3n+2m$，可以跑网络最大流算法。

答案是 $O(nk)$ 级别的，最坏情况就是所有 $a_i$ 均相同。

考虑二分答案，check 就建立一个最大流模型，用 $i,j$ 表示人/天的编号，$S\to i$ 流量为 $k$，$i\to j$ 流量为 $\infty$（第 $i$ 个人在第 $j$ 天上班），$j\to T$ 流量为 $1$，则可行当且仅当最大流为 $nk$。

发现 check 的过程是判断是否满流，并且网络是一张二分图，本质是在判断带权二分图是否存在完美匹配，左部点的权值均为 $k$，右部点的权值均为 $1$。考虑 hall 定理，需要检验每一个左部点集合 $S$ 的邻居集合 $T$ 是否均满足 $|S|\times k\ge |T|$。

令 $f_x$ 表示在第 $x$ 天上班的人的集合，则 $x$ 是 $S$ 的邻居当且仅当 $f_x\cap S=\varnothing$。对于一个 $S$ 这样的 $x$ 的个数可以简单对 $f$ 做子集和并取 $f_{\complement_US}$，于是就可以检验了。$O(n^2k+(nk+n2^n)\log nk)$。

对于一棵确定的树，求出 $deg$，则方案数为 $\prod d_u^{\underline{deg_u}}$。

对于一个 prufer 序列，出现 $x$ 次的点的度数为 $x+1$。

设 prufer 序列中 $u$ 出现了 $c_u$ 次，则方案数为 $\prod d_u^{\underline{c_u+1}}=(\prod d_u)\times(\prod (d_u-1)^{\underline{c_u}})$。

后半部分为从每一个 $(d_u-1)$ 中选出若干个数，总共选 $\sum c_u=n-2$ 个，即总共要在 $s=\sum (d_u-1)$ 个数里面选 $n-2$ 个数，计算 $s^{\underline{n-2}}$ 等价。$O(n)$。

最终会剩下两个分别含 $1,n$ 的完全图。有效加边操作有三类：合并一个连通块到 $1$，合并一个连通块到 $n$，合并两个连通块；另有一种无效加边操作是在同一个连通块里加边。

设 $1$ 号点对应的完全图大小为 $a$，则图的边数为 $x=\binom n2 - a(n-a)$。 $n$ 是奇数时胜负已经确定，只需要判定 $x-m$ 的奇偶性。

进一步地，对于 $n$ 是偶数的情况，胜负也只和 $a$ 的奇偶性有关。我们称初始 $1$ 号点连通块大小奇偶性为 $a$，初始 $n$ 号点奇偶性为 $b$，先手想要必胜的目标条件是 $1$ 号点连通块大小奇偶性为 $A$。

连通块的大小我们并不关心，关心的只是其奇偶性，于是有效操作仅包含合并奇连通块到某一端。不妨进行一些讨论：

• 当 $a,b$ 奇偶性不同，则除了 $1,n$ 以外的两个连通块还有奇数个奇连通块（$n$ 是偶数）。

  • 若 $a=A$，则先手合并一个奇连通块到 $n$ 中，此后先手开始模仿后手的操作就可以保持 $a=A$。具体的，模仿操作指，如果后手没有进行有效操作，则先手合并两个奇连通块（如果不存在，则此后所有操作不改变局面），否则进行一次和后手相反的有效操作。由于从后手开始有偶数个奇连通块，于是模仿操作显然合法。先手必胜。
  • 若 $a\neq A$，则先手合并一个奇连通块到 $1$ 中，此后开始模仿操作。先手必胜。
  • 于是先手可以始终保持 $a=A$，必胜。

• 当 $a,b$ 奇偶性相同，则除了 $1,n$ 以外的两个连通块还有偶数个奇连通块。注意，此时一旦有人进行了有效操作，那么转为上面的情况，对方必胜。

  • 若 $a\neq A$，则先手无法进行有效操作，后手只需要一直合并奇连通块就可以胜，先手必败。
  • 若 $a=A$，则先手只需要一直合并奇连通块就可以胜，后手无法进行有效操作，先手必胜。
  • 于是先手必胜当且仅当初始 $a=A$。

经过讨论，胜负情况只和 $n,m,a,b,A$ 有关。$O(n+m)$。

考虑用黑白染色这个限制代替二分图，对于一个联通二分图只有两种染色方法，最终除以二。

设 $f_S$ 表示 $S$ 内形成二分图（不一定连通）并黑白染色的方案数，$g_S$ 表示 $S$ 内形成联通二分图并黑白染色的方案数，答案就是 $\frac 12g_{U}$。

对于 $f$，直接枚举黑白染色方案，$f_S=\sum_{T\subseteq S}2^{e_{T,S-T}}$，其中 $e_{A,B}$ 表示 $A,B$ 之间的边数，可以预处理 $h_S$ 表示 $S$ 内部的边数计算 $e_{A,B}=h_{A+B}-h_A-h_B$。

对于 $g$，用全部情况减去不连通情况，$g_S=f_S-\sum_{T\subseteq S}g_Tf_{S-T}$，为了不算重需要固定 $S,T$ 中有相同点，例如 lowbit。

$f,g$ 的处理都是子集 dp 的形式，$O(3^n+2^nm)$。