AtCode：Rabbit Exercise（思維）

C - Rabbit Exercise

Time limit : 2sec / Memory limit : 256MB

Score : 800 points

Problem Statement

There are N rabbits on a number line. The rabbits are conveniently numbered 1 through N. The coordinate of the initial position of rabbit i is xi.

The rabbits will now take exercise on the number line, by performing sets described below. A set consists of M jumps. The j-th jump of a set is performed by rabbit aj(2≤aj≤N−1). For this jump, either rabbit aj−1 or rabbit aj+1 is chosen with equal probability (let the chosen rabbit be rabbit x), then rabbit aj will jump to the symmetric point of its current position with respect to rabbit x.

The rabbits will perform K sets in succession. For each rabbit, find the expected value of the coordinate of its eventual position after K sets are performed.

Constraints

• 3≤N≤105
• xi is an integer.
• |xi|≤109
• 1≤M≤105
• 2≤aj≤N−1
• 1≤K≤1018

Input

The input is given from Standard Input in the following format:

N
x1 x2 … xN
M K
a1 a2 … aM
      

Output

Print N lines. The i-th line should contain the expected value of the coordinate of the eventual position of rabbit i after K sets are performed. The output is considered correct if the absolute or relative error is at most 10−9.

Sample Input 1

Copy

3
-1 0 2
1 1
2
      

Sample Output 1

Copy

-1.0
1.0
2.0
      

Rabbit 2 will perform the jump. If rabbit 1 is chosen, the coordinate of the destination will be −2. If rabbit 3 is chosen, the coordinate of the destination will be 4. Thus, the expected value of the coordinate of the eventual position of rabbit 2 is 0.5×(−2)+0.5×4=1.0.

Sample Input 2

Copy

3
1 -1 1
2 2
2 2
      

Sample Output 2

Copy

1.0
-1.0
1.0
      

xi may not be distinct.

Sample Input 3

Copy

5
0 1 3 6 10
3 10
2 3 4
      

Sample Output 3

Copy

0.0
3.0
7.0
8.0
10.0      

題意：坐标軸上有N隻兔子，有M個順序操作，M[i]表示第M[i]隻兔子要選擇跳到左邊相鄰兔子的對稱位置或跳到右邊相鄰兔子的對稱位置，機率相等，這M個操作連續執行K次，輸出最後從左到右每個兔子坐标的期望。

思路：對于兔子x[i]，向左跳有2*x[i-1]-x[i]，向右跳有2*x[i+1]-x[i]，機率各位1/2，得期望x[i-1]+x[i+1]-x[i]，令d[i] = x[i]-x[i-1]，這條期望式子相當于swap(d[i], d[i+1])，那麼連續執行K次，可參考快速幂的做法進行優化。O(NlogK)。

# include <stdio.h>
# include <algorithm>
using namespace std;
typedef long long LL;
const int maxn = 1e5+3;

int a[maxn], d[maxn], c[maxn], b[maxn], tmp[maxn];
LL n, m, k, t;

void qmod()
{
    while(k)
    {
        if(k&1)
        {
            for(int i=1; i<=n; ++i) tmp[i] = b[c[i]];
            for(int i=1; i<=n; ++i) b[i] = tmp[i];
        }
        k >>= 1;
        for(int i=1; i<=n; ++i) tmp[i] = c[c[i]];
        for(int i=1; i<=n; ++i) c[i] = tmp[i];
    }
}

int main()
{
    scanf("%lld",&n);
    for(int i=1; i<=n; ++i)
    {
        scanf("%d",&a[i]);
        d[i] = a[i]-a[i-1];
        tmp[i] = b[i] = c[i] = i;
    }
    scanf("%lld%lld",&m,&k);
    for(int i=1; i<=m; ++i)
    {
        scanf("%d",&t);
        swap(c[t], c[t+1]);
    }
    qmod();
    LL ans = 0;
    for(int i=1; i<=n; ++i)
    {
        ans += (LL)d[b[i]];
        printf("%lld.0\n",ans);
    }
    return 0;
}