AtCoder Grand Contest 006 (AGC006) C - Rabbit Exercise 概率期望

原文链接https://www.cnblogs.com/zhouzhendong/p/AGC006C.html

题目传送门 - AGC006C

题意

  有 $n$ 个兔子,从 $1$ 到 $n$ 编号,第 $i$ 个兔子的初始位置为 $x_i$ ,有 $K$ 次操作,每次操作分 $m$ 步,其中第 $j$ 步用一个数 $a_j$ 描述,这一步的效果是:等概率在 $a_j-1$ 和 $a_j +1$ 中选择一个(假设选择的那个是 $x$),并让兔子 $a_j$ 跳到以兔子 $x$ 为对称中心时,兔子 $a_j$ 的对称位置。求最终所有兔子的位置的期望。

  $n,m\leq 10^5, K\leq 10^{18}, |x_i|\leq 10^9$

题解

  废话1:我好久没写有质量的博客了,现在写一篇。

  废话2:置换方向写反,写成了逆置换,被续走 15 分钟。

  又是一道 AC 之后再证明的题。

  假设兔子 $i$ 跳一步,则:(假设 $E(i)$ 表示兔子 $i$ 的位置这时的期望)

$$E(i) = \frac 12 (2x_{i-1}-x_i) + \frac 12 (2x_{i+1}-x_i) = x_{i-1}+x_{i+1}-x_{i}$$

  于是,可以归纳证明,在跳了若干次之后,满足:

$$E^\prime(i) = \frac 12 (2E(i-1)-E(i)) + \frac 12 (2E(i+1)-E(i)) = E(i-1)+E(i+1)-E(i)$$

  于是每次跳,相当于使

$$x_i^\prime = x_{i-1}+x_{i+1}-x_i$$

  记 $d_i = x_{i+1}-x{i}$ ,可以发现,上述操作的实质就是

$${\rm swap}(d_{i-1},d_i)$$

  于是,我们只需要处理出一组操作的效果,得到一个 $n-1$ 个数的置换,然后做 $K$ 次置换即可。

  这个只需要把置换分解成多个轮换就好了。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=100005;
int n,m,x[N],a[N];
int b[N],vis[N],tmp[N],t;
int ans[N];
LL K;
int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&x[i]);
scanf("%d%lld",&m,&K);
for (int i=1;i<n;i++)
b[i]=i;
for (int i=1;i<=m;i++){
scanf("%d",&a[i]);
swap(b[a[i]-1],b[a[i]]);
}
memset(vis,0,sizeof vis);
for (int i=1;i<n;i++){
if (vis[i])
continue;
vis[i]=1;
tmp[t=1]=i;
for (int j=b[i];j!=i;j=b[j])
vis[tmp[++t]=j]=1;
int d=K%t;
for (int j=1;j<=t;j++)
ans[tmp[j]]=tmp[(j-1+d)%t+1];
}
LL tot=x[1];
printf("%lld\n",tot);
for (int i=1;i<n;i++)
printf("%lld\n",tot+=x[ans[i]+1]-x[ans[i]]);
return 0;
}

  

上一篇:iframe标签书写导致div不显示


下一篇:TRIO-basic指令--FLEXLINK