题目链接：传送门

Description

数轴上有n只兔子，第i只兔子的坐标为xi。 有一组操作，这组操作的第i个操作是要让第ai只兔子等概率的跳到自己关于第ai+1或第ai-1只兔子的对称点。 进行K组操作，求每只兔子最后坐标的期望值。

Hint

N, M <= 1e5, K <= 1e18

Sample Input

3 -1 0 2 1 1 2

Sample Output

-1.0 1.0 2.0

Solution

我们可以把每个点直接跳到进行一次操作后期望到达的点（利用了期望的线性），

那么 ax=12(2ax−1−ax)+12(2ax+1−ax)=ax+1+ax−1−axa_x = \frac{1}{2} (2a_{x - 1} - a_x) + \frac{1}{2} (2a_{x + 1} - a_x) = a_{x + 1} + a_{x - 1} - a_x

如果我们把原序列做一个差分的话

ax−1,ax,ax+1a_{x - 1}, a_x, a_{x + 1}---------------------------> ax−1−ax−2,ax−ax−1,ax+1−axa_{x - 1} - a_{x - 2}, a_x - a_{x - 1}, a_{x + 1} - a_x

ax−1,ax+1+ax−1−ax,ax+1a_{x - 1}, a_{x + 1} + a_{x - 1} - a_x, a_{x + 1} ---> ax−1−ax−2,ax+1−ax,ax−ax−1a_{x - 1} - a_{x - 2}, a_{x + 1} - a_x, a_x - a_{x - 1}

就能发现实际上就是把xx和x+1x + 1交换了位置

然后我们用一个数组记录一下位置即可

对于K≤1018K\le10^{18}，我们可以用一个类似快速幂的东西（或者说是倍增）去做

里面有个小细节就是每次更新数组的时候要先用Tmp数组存一下，然后再复制到原数组上，否则有可能跳来跳去

出问题

还有就是要开long long，int会炸

Summary

这道题早就听说过了特别难，今天自己做的话显然是看了题解的。自己做的时候就完全没有一点头绪，开始想到了对于每次操作可以直接跳到期望的那个点，但是不知道怎么处理那么大的K。这道题也算是积累一个方法吧。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const LL Maxn = 100000 + 100;
LL A[Maxn], d[Maxn], P[Maxn];
LL Tmp[Maxn], Ans[Maxn];
LL N, M;
LL K;
inline void Pow()
{
    LL b = K;
    for (LL i = 1; i <= N; ++i) Ans[i] = i;
    while (b)
    {
        if (b & 1)
        {
            for (LL i = 1; i <= N; ++i) Tmp[i] = Ans[P[i]];
            for (LL i = 1; i <= N; ++i) Ans[i] = Tmp[i];
        }
        for (LL i = 1; i <= N; ++i) Tmp[i] = P[P[i]];
        for (LL i = 1; i <= N; ++i) P[i] = Tmp[i];
        b >>= 1;
    }
    for (LL i = 1; i <= N; ++i) Tmp[i] = d[Ans[i]];
    for (LL i = 1; i <= N; ++i) d[i] = Tmp[i];
}
int main()
{
#ifdef hk_cnyali
    freopen("C.in", "r", stdin);
    freopen("C.out", "w", stdout);
#endif
    scanf("%lld", &N);
    for (LL i = 1; i <= N; ++i)
        scanf("%lld", &A[i]), d[i] = A[i] - A[i - 1];
    scanf("%lld %lld", &M, &K);
    for (LL i = 1; i <= N; ++i) P[i] = i;
    for (LL i = 1; i <= M; ++i)
    {
        LL x; scanf("%lld", &x);
        swap(P[x], P[x + 1]);
    }
    Pow();
    LL Sum = 0;
    for (LL i = 1; i <= N; ++i)
    {
        Sum += d[i];
        cout<<Sum<<endl;
    }
    return 0;
}