题解 AT2164 【Rabbit Exercise】
yybyyb
2018-09-20 19:58:12
无论怎么样任何一个点每次操作一定是变成$2a_{x-1}(a_{x+1})-a_x$。设$f_x$表示$x$这个点当前的期望，假设当前点要进行依次变换，那么期望为$\frac{1}{2}((2f_{x-1}-f_x)+(2f_{x+1}-f_x))=f_{x+1}+f_{x-1}-f_x$。
好的，然后进行$K$轮就不会了。怎么办呢？(当然是点开题解了啊)。闲着无聊来差分一下，设$d_i=f_i-f_{i-1}$，那么执行完一次操作之后：$d_i=(f_{i-1}+f_{i+1}-f_i)-f_{i-1}=f_{i+1}-f_i$，$d_{i+1}=f_{i+1}-(f_{i-1}+f_{i+1}-f_i)=f_i-f_{i-1}$。
好啊，一次操作等价于交换$d_i,d_{i+1}$，那么我们只要记录一下做完一轮操作之后$d_i$都到哪里去了，然后就可以倍增了。
```cpp
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
#define MAX 100100
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int n,x[MAX],m,d[MAX],ans[MAX],tmp[MAX];ll K;
double a[MAX];
int main()
{
n=read();
for(int i=1;i<=n;++i)x[i]=read();
m=read();cin>>K;
for(int i=1;i<=n;++i)d[i]=i,ans[i]=i;
for(int i=1;i<=m;++i)
{
int x=read();
swap(d[x],d[x+1]);
}
while(K)
{
if(K&1)
{
for(int i=1;i<=n;++i)tmp[i]=ans[d[i]];
for(int i=1;i<=n;++i)ans[i]=tmp[i];
}
for(int i=1;i<=n;++i)tmp[i]=d[d[i]];
for(int i=1;i<=n;++i)d[i]=tmp[i];
K>>=1;
}
for(int i=1;i<=n;++i)a[i]=x[ans[i]]-x[ans[i]-1];
for(int i=1;i<=n;++i)printf("%.1lf\n",a[i]+=a[i-1]);
return 0;
}
```