[数学记录]AT2164 [AGC006C] Rabbit Exercise

· · 个人记录

题意 ： 数轴上有 n 只兔子，编号为 1\sim n ，第 i 只兔子的初始坐标为 x_i。

兔子会以以下的方式在数轴上行动 ：一轮包含 m 次跳跃，第 j 次跳跃中，是兔子 a_j 从兔子 a_j-1 和兔子 a_j+1 中等概率的选一个。

（保证 2\leq a_j\leq n-1）

记选的兔子坐标为 x ，那么 a_j 号兔子会跳到它当前坐标关于 x 的对称点。

（注意，即使兔子的位置顺序变化了，但是编号仍保持不变）

兔子会进行 k 轮跳跃，对每个兔子，求出它最后坐标的期望值。以实数的形式输出。

------------ 点 $x_0$ 关于 $x_1$ 的对称点为 $2x_1-x_0$ ，这是线性的，所以可以直接维护期望。 现在问题变为，每次给定 $p$ 令 $x_{p}'=x_{p+1}+x_{p-1}-x_p$ ，求将这组 $m$ 个操作重复 $k$ 轮，最终得到的 $x$ 数组。 （不难发现答案其实一定是整数） 这里有三项，较为复杂。考虑差分，记 $d_i=x_i-x_{i-1}$。 则每次操作后 $\begin{cases}d_p'=(x_{p+1}+x_{p-1}-x_p)-x_{p-1}=x_{p+1}-x_p=d_{p+1}\\ d_{p+1}'=x_{p+1}-(x_{p+1}+x_{p-1}-x_p)=x_p-x_{p-1}=d_p\end{cases}

实际上相当于交换了 d_p 与 d_{p+1}。

记录这些交换构成的映射，接下来就是计算映射的 k 次复合，容易做到 O(n\log k)。

注意答案可能爆 int。

#include<algorithm>
#include<cstdio>
#define ll long long
#define MaxN 100500
using namespace std;
int buf[MaxN],sav[MaxN];
void pow(int *a,int n,ll t)
{
  for (int i=1;i<=n;i++){buf[i]=a[i];a[i]=i;}
  while(t){
    if (t&1)for (int i=1;i<=n;i++)a[i]=buf[a[i]];
    for (int i=1;i<=n;i++)sav[i]=buf[i];
    for (int i=1;i<=n;i++)buf[i]=sav[buf[i]];
    t>>=1;
  }
}
int n,m,p[MaxN];
ll x[MaxN],ans[MaxN],k;
int main()
{
  scanf("%d",&n);
  for (int i=1;i<=n;i++)scanf("%lld",&x[i]);
  for (int i=n;i;i--)x[i]-=x[i-1];
  scanf("%d%lld",&m,&k);
  for (int i=1;i<=n;i++)p[i]=i;
  for (int i=1,j;i<=m;i++){
    scanf("%d",&j);
    swap(p[j],p[j+1]);
  }
  pow(p,n,k);
  for (int i=1;i<=n;i++){
    ans[i]=ans[i-1]+x[p[i]];
    printf("%lld\n",ans[i]);
  }return 0;
}