agc006c

题意：有n个兔子，初始时第i个兔子在xi位置，每组有m次跳跃，每组的第i次跳跃为兔子$$a_i$$等概率选$$a_i-1$$或$$a_i+1$$,然后兔子$$a_i$$的位置变为原位置关于选择的兔子位置对称的位置。求进行K组后第i个兔子的期望位置。

每次跳跃相当于把兔子从位置 $$X_i$$ 变为$$X_{i-1} +X_{i+1}-X_i$$

差分之后相当于交换两个数的位置
直接对每个轮换求

#include <bits/stdc++.h>
using namespace std;
#define N 1100000
#define ll long long
ll K;
int n,m,top;
int a[N],p[N],pos[N],vis[N],fin[N],st[N];
ll v[N],v1[N];
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&v[i]),p[i]=i;
    scanf("%d%lld",&m,&K);
    for(int i=1;i<=m;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)
        swap(p[a[i]],p[a[i]+1]);
    for(int i=1;i<=n;i++)pos[p[i]]=i;
    for(int i=1,now;i<=n;i++)if(!vis[i])
    {
        st[0]=i;vis[i]=1;top=1;
        now=pos[i];
        while(now!=i)
        {
            st[top]=now;vis[now]=1;top++;
            now=pos[now];
        }
        int t=K%top;
        for(int j=0;j<top;j++)
            fin[st[(j+t)%top]]=st[j];
    }
    v1[1]=v[1];
    for(int i=2;i<=n;i++)v1[i]=v[i]-v[i-1];
    for(int i=1;i<=n;i++)v[i]=v1[fin[i]];
    v1[1]=v[1];
    for(int i=2;i<=n;i++)v1[i]=v[i]+v1[i-1];
    for(int i=1;i<=n;i++)
        printf("%lld.0\n",v1[i]);
    return 0;
}