题解 AT2164 【Rabbit Exercise】
ezoixx130
2019-09-11 20:37:06
考虑跳第 $i$ 个点的时候，如果往左跳会跳到 $a_{i-1}-(a_{i}-a_{i-1})$ 即 $2a_{i-1}-a_i$ 的位置上，如果往右跳会跳到 $a_{i+1}+(a_{i+1}-a_i)$ 即 $2a_{i+1}-a_i$ 的位置上。
所以对 $i$ 个点进行操作的话，期望位置会变成 $\large \frac{2a_{i-1}-a_i+2a_{i+1}-a_i}{2}$ 即 $\large a_{i-1}-a_i+a_{i+1}$。
但是这种操作不好维护，因为你要做 $10^{18}$ 轮这样的操作，暴力处理显然不是正解。
如果将期望序列差分，考虑对 $i$ 进行操作的时候，设原本第 $i-1,i,i+1$ 号点的位置期望分别为 $a,b,c$，那么差分序列为 $b-a,c-b$。对 $i$ 号点进行完操作以后，期望序列变为 $a,a-b+c,c$，差分序列为 $c-b,b-a$。也就是说，对一个点进行操作等价于在期望的差分序列上交换两个数。
那么这样就好维护多了，因为这样的一轮操作相当于对差分序列进行一个置换。要做 $10^{18}$ 轮这样的操作，对置换进行快速幂即可。
时间复杂度：$O(n\log k)$
代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100010
int n,m,a[MAXN],ans[MAXN],res[MAXN],tmp[MAXN];
long long k;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",a+i);
for(int i=1;i<n;++i)ans[i]=i;
scanf("%d%lld",&m,&k);
for(int i=1;i<=m;++i)
{
int x;
scanf("%d",&x);
swap(ans[x],ans[x-1]);
}
for(int i=1;i<n;++i)res[i]=i;
while(k)
{
if(k&1)
for(int i=1;i<n;++i)res[i]=ans[res[i]];
for(int i=1;i<n;++i)tmp[i]=ans[ans[i]];
for(int i=1;i<n;++i)ans[i]=tmp[i];
k>>=1;
}
long long sum=a[1];
for(int i=1;i<=n;++i)
{
printf("%lld.0\n",sum);
sum+=a[res[i]+1]-a[res[i]];
}
}
```