【AGC006 C】Rabbit Exercise

题意

　　有 (n) 只兔子在数轴上，第 (i) 只兔子的初始坐标为整数 (x_i)。
　　现在这些兔子会按照下面的规则做体操。每一轮体操都由 (m) 次跳跃组成：在第 (j) 次跳跃时，第 (a_j (2le a_jle n-1)) 只兔子会等概率随机选择第 (a_j-1) 或 (a_j+1) 只兔子中的一只，设选择的兔子的坐标为 (x)，然后跳到当前位置关于 (x) 的对称点。
　　求这些兔子会按顺序做 (k) 轮体操后，每只兔子的期望坐标。
　　(n,mle 10^5)
　　(kle 10^{18})
　　(|x_i|le 10^9)

题解

　　设某个时刻第 (i) 只兔子的期望坐标为 (f_i)，则第 (i) 只兔子跳跃后，期望坐标为 (f_i' = frac{1}{2} (2f_{i-1}-f_i) + frac{1}{2} (2f_{i+1}-f_i) = f_{i-1}+f_{i+1}-f_i)
　　这个看上去没啥规律，但发现这个式子只跟 (i-1,i,i+1) 有关，于是试着考虑差分的变化。令 (g_i = f_i - f_{i-1})，则 (g_i' = f_i' - f_{i-1} = f_{i-1}+f_{i+1}-f_i-f_{i-1} = f_{i+1}-f_i)
　　(g_i') 似乎就是 (g_{i+1})？
　　我们再考虑 (g_{i+1}')，发现 (g_{i+1}' = f_{i+1} - f_i' = f_{i+1} - f_{i-1} - f_{i+1} + f_i = f_i - f_{i-1})
　　也就是说，一只兔子跳一下，只是交换了两个差分值？

　　故我们可以把 (a_j) 转化成差分形式，然后加速做 (k) 次体操。
　　加速的方式较多，可以直接倍增，也可以计算轮换。由于后者更优，这里用后者。
　　我们发现，做一套体操 相当于把 (a) 数组做一个轮换。
　　那做哪些轮换呢？就是每一只兔子跳跃时，设这只兔子编号为 (i)，则交换 (a_i) 和 (a_{i+1})。
　　我们知道，轮换是由若干个环组成的，故可以快速计算一个位置沿其所在的环转移 (k) 次后会到达哪个位置，只要我们知道环的大小。
　　具体见代码吧。
　　最后需要把 (a_j) 从差分形式转回正常形式，每个位置的正常值 就是差分值的前缀和，
　　复杂度 (O(n))。

#include<bits/stdc++.h>
#define ll long long
#define N 100002
using namespace std;
inline ll read(){
    ll x=0; bool f=1; char c=getchar();
    for(;!isdigit(c); c=getchar()) if(c=='-') f=0;
    for(; isdigit(c); c=getchar()) x=(x<<3)+(x<<1)+(c^'0');
    if(f) return x;
    return 0-x;
}
int n,m; ll k;
ll a[100010]; int vis[N],to[N],cir[N];
ll ans[100010];
int main(){
    n=read();
    ll lst=0;
    for(int i=1; i<=n; i++){
        a[i]=read()-lst;
        lst+=a[i];
        to[i]=i;
    }
    m=read(),k=read();
    int x;
    for(int i=1; i<=m; i++) x=read(),swap(to[x],to[x+1]);
    for(int i=1; i<=n; i++) if(!vis[i]){
        int cnt=0,j;
        for(j=i; !vis[j]; j=to[j]) vis[j]=1,cir[++cnt]=j;
        for(j=1; j<=cnt; j++) ans[cir[j]] = a[cir[(j+k-1)%cnt+1]];
    }
    for(int i=1; i<=n; i++){
        printf("%lld.0n",ans[i]+=ans[i-1]);
    }
    return 0;
}