题解 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都到哪里去了，然后就可以倍增了。

#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;
}