【AGC006 C】Rabbit Exercise

题意

　　有 \(n\) 只兔子在数轴上，第 \(i\) 只兔子的初始坐标为整数 \(x_i\)。

　　现在这些兔子会按照下面的规则做体操。每一轮体操都由 \(m\) 次跳跃组成：在第 \(j\) 次跳跃时，第 \(a_j (2\le a_j\le n-1)\) 只兔子会等概率随机选择第 \(a_j-1\) 或 \(a_j+1\) 只兔子中的一只，设选择的兔子的坐标为 \(x\)，然后跳到当前位置关于 \(x\) 的对称点。

　　求这些兔子会按顺序做 \(k\) 轮体操后，每只兔子的期望坐标。

　　\(n,m\le 10^5\)

　　\(k\le 10^{18}\)

　　\(|x_i|\le 10^9\)

题解

　　设某个时刻第 \(i\) 只兔子的期望坐标为 \(f_i\)，则第 \(i\) 只兔子跳跃后，期望坐标为 \(f_i' = \frac{1}{2} (2f_{i-1}-f_i) + \frac{1}{2} (2f_{i+1}-f_i) = f_{i-1}+f_{i+1}-f_i\)

　　这个看上去没啥规律，但发现这个式子只跟 \(i-1,i,i+1\) 有关，于是试着考虑差分的变化。令 \(g_i = f_i - f_{i-1}\)，则 \(g_i' = f_i' - f_{i-1} = f_{i-1}+f_{i+1}-f_i-f_{i-1} = f_{i+1}-f_i\)

　　\(g_i'\) 似乎就是 \(g_{i+1}\)？

　　我们再考虑 \(g_{i+1}'\)，发现 \(g_{i+1}' = f_{i+1} - f_i' = f_{i+1} - f_{i-1} - f_{i+1} + f_i = f_i - f_{i-1}\)

　　也就是说，一只兔子跳一下，只是交换了两个差分值？

　　故我们可以把 \(a_j\) 转化成差分形式，然后加速做 \(k\) 次体操。

　　加速的方式较多，可以直接倍增，也可以计算轮换。由于后者更优，这里用后者。

　　我们发现，做一套体操相当于把 \(a\) 数组做一个轮换。

　　那做哪些轮换呢？就是每一只兔子跳跃时，设这只兔子编号为 \(i\)，则交换 \(a_i\) 和 \(a_{i+1}\)。

　　我们知道，轮换是由若干个环组成的，故可以快速计算一个位置沿其所在的环转移 \(k\) 次后会到达哪个位置，只要我们知道环的大小。

　　具体见代码吧。

　　最后需要把 \(a_j\) 从差分形式转回正常形式，每个位置的正常值就是差分值的前缀和。

　　复杂度 \(O(n)\)。

#include<bits/stdc++.h>

#define ll long long

#define N 100002

using namespace std;

inline ll read(){

    ll x=0; bool f=1; char c=getchar();

    for(;!isdigit(c); c=getchar()) if(c=='-') f=0;

    for(; isdigit(c); c=getchar()) x=(x<<3)+(x<<1)+(c^'0');

    if(f) return x;

    return 0-x;

}

int n,m; ll k;

ll a[100010]; int vis[N],to[N],cir[N];

ll ans[100010];

int main(){

    n=read();

    ll lst=0;

    for(int i=1; i<=n; i++){

        a[i]=read()-lst;

        lst+=a[i];

        to[i]=i;

    }

    m=read(), k=read();

    int x;

    for(int i=1; i<=m; i++) x=read(), swap(to[x],to[x+1]);

    for(int i=1; i<=n; i++) if(!vis[i]){

        int cnt=0, j;

        for(j=i; !vis[j]; j=to[j]) vis[j]=1, cir[++cnt]=j;

        for(j=1; j<=cnt; j++) ans[cir[j]] = a[cir[(j+k-1)%cnt+1]];

    }

    for(int i=1; i<=n; i++){

        printf("%lld.0\n", ans[i]+=ans[i-1]);

    }

    return 0;

}

巴特西

【AGC006 C】Rabbit Exercise

题意

题解

最新文章

热门文章