题目描述

　　有\(n\)只兔子站在数轴上。为了方便，将这些兔子标号为\(1\ldots n\)。第\(i\)只兔子的初始位置为\(a_i\)。

　　现在这些兔子会按照下面的规则做若干套体操。每一套体操由\(m\)次跳跃组成；在第\(j\)次跳跃的时候，第\(c_j(2≤c_j≤n−1)\)只兔子会等概率随机选择第\(c_j−1\)或\(c_j+1\)只兔子中的一只（不妨设选择了第\(x\)只兔子），然后跳当前位置到关于第\(x\)只兔子对称的点。

　　这些兔子会按顺序做\(k\)套相同的体操。现在请你求出，每一只兔子做完\(k\)套体操之后最终位置坐标的期望值。

　　\(n,m\leq 100000,k\leq {10}^{18}\)

题解

　　每次操作\(a_x=\frac{1}{2}(2a_{x-1}-a_x)+\frac{1}{2}(2a_{x+1}-a_x)=a_{x-1}+a_{x+1}-a_x\)

　　可以发现这是一个线性变换，可以直接计算。

　　那么有什么规律吗？

　　假设有三个数\(a_1,a_2,a_3\)，\(c_1=2\)。

　　变换后会得到\(a_1,a_1+a_3-a_2,a_3\)。

　　我们差分一下：

　　相当于把\(a_{c_1},a_{c_1+1}\)交换了一下。

　　所以可以直接把\(m\)次操作看成\(m\)个交换，做完这些操作看成\(1\)到\(n\)的置换。把整个置换拆成很多个轮换，直接在每个轮换上面走\(k\)步就行了。

　　时间复杂度：\(O(n+m)\)

代码

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<ctime>

#include<utility>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> pii;

ll a[100010];

int c[100010];

int b[100010];

int d[100010];

ll ans[100010];

int main()

{

#ifdef DEBUG

	freopen("b.in","r",stdin);

	freopen("b.out","w",stdout);

#endif

	int n;

	scanf("%d",&n);

	int i;

	ll sum=0;

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

	{

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

		a[i]-=sum;

		sum+=a[i];

		c[i]=i;

	}

	int m;

	ll k;

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

	int x;

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

	{

		scanf("%d",&x);

		swap(c[x],c[x+1]);

	}

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

		if(!b[i])

		{

			int cnt=0;

			int j;

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

			{

				b[j]=1;

				d[++cnt]=j;

			}

			for(j=1;j<=cnt;j++)

				ans[d[j]]=a[d[(j+k-1)%cnt+1]];

		}

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

	{

		ans[i]+=ans[i-1];

		printf("%lld.0\n",ans[i]);

	}

	return 0;

}