[AT2164] [agc006_c] Rabbit Exercise

题目链接

AtCoder：https://agc006.contest.atcoder.jp/tasks/agc006_c

洛谷：https://www.luogu.org/problemnew/show/AT2164

Solution

注意到设第(i)个点的期望位置为(p_i)，由中点公式可知这个点移动一次的期望位置变成了：

[p_i'=frac{2p_{i+1}-p_i+2p_{i-1}-p_i}{2}=p_{i+1}+p_{i-1}-p_i ]

考虑这个序列的差分数组(Delta p_i=p_i-p_{i-1})，考虑第(i)个位置发生一次变换会发生什么：

[Delta p_{i}'=p'_{i}-p_{i-1}=p_{i+1}-p_i=Delta p_{i+1}\ Delta p_{i+1}'=p_{i+1}-p'_i=p_{i}-p_{i-1}=Delta p_{i} ]

其中(Delta p',p')表示变换之后的值，未加上标表示之前的值。

那么可以注意到这次变换实质上就是({ m swap}(Delta p_i,Delta p_{i+1}))。

由于每轮操作都是一样的，那么我们可以把每轮操作写成一个置换，然后处理出倍增数组暴力跳就好了。

#include<bits/stdc++.h>
using namespace std;

#define int long long 

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}

void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('
');}

#define lf double
#define ll long long 

const int maxn = 1e5+10;
const int inf = 1e9;
const lf eps = 1e-8;

int p[maxn],d[maxn],n,m,k,fa[maxn][61],a[maxn],b[maxn];

signed main() {
	read(n);for(int i=1;i<=n;i++) read(p[i]),d[i]=p[i]-p[i-1],a[i]=i;
	for(int i=1;i<=n;i++) b[i]=i;
	read(m),read(k);
	for(int i=1,x;i<=m;i++) read(x),swap(a[x],a[x+1]);
	for(int i=1;i<=n;i++) fa[i][0]=a[i];
	for(int i=1;i<=60;i++)
		for(int x=1;x<=n;x++)
			fa[x][i]=fa[fa[x][i-1]][i-1];
	for(int t=k,x=1;x<=n;x++,t=k)
		for(int i=60;~i;i--)
			if(t>=(1ll<<i)) t-=(1ll<<i),b[x]=fa[b[x]][i];
	for(int i=1;i<=n;i++) a[i]=d[b[i]];
	for(int i=1;i<=n;i++) a[i]+=a[i-1],printf("%lld.0
",a[i]);
	return 0;
}