[数学记录]AT2164 [AGC006C] Rabbit Exercise
command_block
2021-04-22 10:09:25
**题意** ： 数轴上有 $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$ 轮跳跃，对每个兔子，求出它最后坐标的期望值。以实数的形式输出。
$n,m\leq 10^5,k\leq 10^{18}$。
------------
点 $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`。
```cpp
#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;
}
```