原文链接https://www.cnblogs.com/zhouzhendong/p/AGC006C.html

题目传送门 - AGC006C

题意

　　有 $n$ 个兔子，从 $1$ 到 $n$ 编号，第 $i$ 个兔子的初始位置为 $x_i$ ，有 $K$ 次操作，每次操作分 $m$ 步，其中第 $j$ 步用一个数 $a_j$ 描述，这一步的效果是：等概率在 $a_j-1$ 和 $a_j +1$ 中选择一个（假设选择的那个是 $x$），并让兔子 $a_j$ 跳到以兔子 $x$ 为对称中心时，兔子 $a_j$ 的对称位置。求最终所有兔子的位置的期望。

　　$n,m\leq 10^5, K\leq 10^{18}, |x_i|\leq 10^9$

题解

　　废话1：我好久没写有质量的博客了，现在写一篇。

　　废话2：置换方向写反，写成了逆置换，被续走 15 分钟。

　　又是一道 AC 之后再证明的题。

　　假设兔子 $i$ 跳一步，则：（假设 $E(i)$ 表示兔子 $i$ 的位置这时的期望）

$$E(i) = \frac 12 (2x_{i-1}-x_i) + \frac 12 (2x_{i+1}-x_i) = x_{i-1}+x_{i+1}-x_{i}$$

　　于是，可以归纳证明，在跳了若干次之后，满足：

$$E^\prime(i) = \frac 12 (2E(i-1)-E(i)) + \frac 12 (2E(i+1)-E(i)) = E(i-1)+E(i+1)-E(i)$$

　　于是每次跳，相当于使

$$x_i^\prime = x_{i-1}+x_{i+1}-x_i$$

　　记 $d_i = x_{i+1}-x{i}$ ，可以发现，上述操作的实质就是

$${\rm swap}(d_{i-1},d_i)$$

　　于是，我们只需要处理出一组操作的效果，得到一个 $n-1$ 个数的置换，然后做 $K$ 次置换即可。

　　这个只需要把置换分解成多个轮换就好了。

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=100005;

int n,m,x[N],a[N];

int b[N],vis[N],tmp[N],t;

int ans[N];

LL K;

int main(){

	scanf("%d",&n);

	for (int i=1;i<=n;i++)

		scanf("%d",&x[i]);

	scanf("%d%lld",&m,&K);

	for (int i=1;i<n;i++)

		b[i]=i;

	for (int i=1;i<=m;i++){

		scanf("%d",&a[i]);

		swap(b[a[i]-1],b[a[i]]);

	}

	memset(vis,0,sizeof vis);

	for (int i=1;i<n;i++){

		if (vis[i])

			continue;

		vis[i]=1;

		tmp[t=1]=i;

		for (int j=b[i];j!=i;j=b[j])

			vis[tmp[++t]=j]=1;

		int d=K%t;

		for (int j=1;j<=t;j++)

			ans[tmp[j]]=tmp[(j-1+d)%t+1];

	}

	LL tot=x[1];

	printf("%lld\n",tot);

	for (int i=1;i<n;i++)

		printf("%lld\n",tot+=x[ans[i]+1]-x[ans[i]]);

	return 0;

}