Problem:
 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 x_i .  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 a_j ( 2≤a_j≤N-1 ).
For this jump, either rabbit a_j-1 or rabbit a_j+1 is chosen with equal probability (let the chosen rabbit be rabbit x ), then rabbit a_j 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≤10^5  x_i is an integer.  |x_i|≤10^9  1≤M≤10^5  2≤a_j≤N-1  1≤K≤10^{18}         Input The input is given from Standard Input in the following format:  N  x_1  x_2  ...  x_N  M  K  a_1  a_2  ...  a_M       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 3
-1 0 2
1 1
2      Sample Output 1 -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 3
1 -1 1
2 2
2 2      Sample Output 2 1.0
-1.0
1.0  x_i may not be distinct.       Sample Input 3 5
0 1 3 6 10
3 10
2 3 4      Sample Output 3 0.0
3.0
7.0
8.0
10.0

Solution (Python):
import numpy as np


def test(n, xxx, m, k, aaa):
    
    print(np.diff(xxx))
    for _ in range(k):
        for a in aaa:
            x, y, z = xxx[a - 2:a + 1]
            b = x - (y - x)
            c = z + (z - y)
            xxx[a - 1] = (b + c) // 2
        
        print(np.diff(xxx))


n = int(input())
xxx = list(map(int, input().split()))
m, k = map(int, input().split())
aaa = list(map(int, input().split()))

doubling = np.arange(n - 1, dtype=np.int64)
for a in aaa:
    doubling[a - 2], doubling[a - 1] = doubling[a - 1], doubling[a - 2]

perm = np.arange(n - 1, dtype=np.int64)
while k:
    if k & 1:
        perm = perm[doubling]
    doubling = doubling[doubling]
    k >>= 1

diff = np.diff(xxx)[perm]
diff = np.insert(diff, 0, xxx[0])
print('\n'.join(map(str, diff.cumsum())))

Solution (Python):
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main(N, M, K, X, A):
    def compute_perm(A):
        P = np.arange(N - 1)
        for i in A:
            P[i - 2], P[i - 1] = P[i - 1], P[i - 2]
        return P

    def power(P, K):
        Q = P.copy()
        x = np.arange(len(P), dtype=np.int32)
        while K:
            if K & 1:
                x = x[Q]
            Q = Q[Q]
            K >>= 1
        return x

    P = compute_perm(A)
    P = power(P, K)
    D = X[1:] - X[:-1]
    D = D[P]
    ret = np.zeros(N, np.int64)
    ret[0] = X[0]
    ret[1:] = np.cumsum(D) + X[0]
    return ret

signature = '(i8,i8,i8,i8[:],i4[:])'
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', signature)(main)
    cc.compile()

from my_module import main

N = int(readline())
X = np.array(readline().split(), np.int64)
M, K = map(int, readline().split())
A = np.array(readline().split(), np.int32)

x = main(N, M, K, X, A)
print('\n'.join(map(str, x.tolist())))

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

"""
・対象のうさぎの期待値だけ分かれば、次時点での期待値が分かる
・期待値の差分Yを持つ。操作は、Y[i-1]とY[i]の交換
"""

N = int(readline())
X = np.zeros(N+1,np.int64)
X[1:] = readline().split()
M,K = map(int,readline().split())
A = list(map(int,read().split()))

Y = np.diff(X)


P = list(range(N))
for a in A:
    P[a],P[a-1] = P[a-1],P[a]
P = np.array(P)

def mult_perm(P,Q):
    return P[Q]

def power_perm(P,N):
    if N == 0:
        return np.arange(len(P))
    Q = power_perm(P,N//2)
    Q = mult_perm(Q,Q)
    return mult_perm(P,Q) if N & 1 else Q

Q = power_perm(P,K)

newY = Y[Q]
newX = np.cumsum(newY)

print('\n'.join(newX.astype(str)))

Solution (Python):
import sys
readline = sys.stdin.readline

def merge(A, B):
    N = len(A)
    res = [B[A[i]] for i in range(N)]
    return res

N = int(readline())

X = list(map(int, readline().split()))
M, K = map(int, readline().split())
A = list(map(lambda x:int(x)-1, readline().split()))
Y = [x2 - x1 for x1, x2 in zip(X, X[1:])]

 
P = list(range(N))
for a in A:
    P[a], P[a+1] = P[a+1], P[a]
stack = [P]
for _ in range(65):
    stack.append(merge(stack[-1], stack[-1]))

E = list(range(N))
for i in range(K.bit_length()):
    if (1<<i) & K:
        E = merge(E, stack[i])

Ans = [0]*N
Ans[0] = X[0]
for i in range(1, N):
    Ans[i] = Ans[i-1] + Y[E[i]-1]
print('\n'.join(map(str, Ans)))

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

"""
両端の位置が不変。x,y,z -> x,x+z-y,zを繰り返すが、階差数列で見るとswapに相当する。
"""

import numpy as np

N = int(input())
X = [int(x) for x in input().split()]
M,K = map(int,input().split())
A = [int(x) for x in input().split()]

P = list(range(N))
for a in A:
    P[a-1],P[a] = P[a],P[a-1]

P = np.array(P,dtype=np.int32)

def power(P,n):
    if n == 1:
        return P
    Q = power(P,n//2)
    Q = Q[Q]
    return P[Q] if n&1 else Q

Q = power(P,K)

diff = np.diff([0] + X)
answer = diff[Q].cumsum()
print('\n'.join(answer.astype(str)))

Solution (Python):
from numpy import*
n,*a=map(int,open(0).read().split())
*s,=t=arange(n-1)
for i in a[-a[n]:]:t[[i-2,i-1]]=t[[i-1,i-2]]
k=a[n+1]
while k:s=[s,t[s]][k%2];t=t[t];k//=2
print(*cumsum(a[:1]+list(diff(a[:n])[s])))

Solution (Python):
from numpy import*
n,*a=map(int,open(0).read().split())
t=arange(n-1)
*s,=t
for i in a[-a[n]:]:t[i-2],t[i-1]=t[i-1],t[i-2]
k=a[n+1]
while k:
    if k%2:s=t[s]
    t=t[t]
    k//=2
print(*cumsum(a[:1]+list(diff(a[:n])[s])))

Solution (Python):
n = int(input())
x = list(map(int, input().split()))
g = [x[i+1]-x[i] for i in range(n-1)]
m, k = map(int, input().split())
A = list(map(int, input().split()))
t = list(range(n-1))
for a in A:
	t[a-2], t[a-1] = t[a-1], t[a-2]
s = list(range(n-1))
while k > 0:
	if k&1:
		s = [s[t[i]] for i in range(n-1)]
	t = [t[t[i]] for i in range(n-1)]
	k >>= 1
new_g = [g[s[i]] for i in range(n-1)]
ans = [x[0]]
for i in range(n-1):
	ans.append(ans[-1] + new_g[i])
print(*ans, sep="\n")

Solution (Python):
N=int(input())
X=[int(i) for i in input().split()]
dX=[]
for i in range(N-1):
  dX.append(X[i+1]-X[i])
M,K=map(int,input().split())
A=[int(i)-2 for i in input().split()]
Swap=[list(range(N-1)) for i in range(61)]
for a in A:
  Swap[0][a],Swap[0][a+1]=Swap[0][a+1],Swap[0][a]
for k in range(60):
  for i in range(N-1):
    Swap[k+1][i]=Swap[k][Swap[k][i]]
C=list(range(N-1))
for k in range(61)[::-1]:
  if K&(1<<k):
    for i in range(N-1):
      C[i]=Swap[k][C[i]]
new_dX=[0]*(N-1)
for i in range(N-1):
  new_dX[i]=dX[C[i]]
S=X[0]
print(X[0])
for i in range(N-1):
  S+=new_dX[i]
  print(S)

Solution (Python):
n = int(input())
x = list(map(int,input().split()))
m,k = map(int,input().split())
a = list(map(int,input().split()))
b = []
x2 = []
c = []
for i in range(1,n):
  b.append(i-1)
  x2.append(x[i]-x[i-1])
for i in range(m):
  to = a[i]-1
  b[to],b[to-1] = b[to-1],b[to]
c = [-1] * (n-1)
for i in range(n-1):
  c[b[i]] = i
for i in range(60):
  x3 = [0]*(n-1)
  if k&(1<<i):
    for i in range(n-1):
      x3[c[i]] = x2[i]
    x2 = x3
  c2 = [-1] * (n-1)
  for i in range(n-1):
    c2[i] = c[c[i]] 
  c = c2
s = x[0]
print(s)
for i in x2:
  s += i
  print(s)

Solution (Python):
def process(x, a, k):
    n = len(x)
    f = range(0, n)
    for i in a:
        f[i], f[i+1] = f[i+1], f[i]
    
    b = 1
    while b<=k:
        if (k&b)!=0:
            t = [0 for i in xrange(n)]
            for i in xrange(n):
                t[i] = x[f[i]]
            x = [i for i in t]
            
        t = [0 for i in f]
        for i in xrange(n):
            t[i] = f[f[i]]
        f = [i for i in t]
        
        b <<= 1
    return x

def main():
    n = int(raw_input().strip())
    x = [int(i) for i in raw_input().strip().split()]
    for i in xrange(len(x)-1, 0, -1):
        x[i] = x[i]-x[i-1]
    m, k = [int(i) for i in raw_input().strip().split()]
    a = [int(i) for i in raw_input().strip().split()]
    for i in xrange(len(a)):
        a[i] -= 2
    r = process(x[1:], a, k)
    print x[0]
    for i in xrange(1, len(x)):
        x[i] = x[i-1]+r[i-1]
        print x[i]

if __name__ == '__main__':
    main()

Solution (Python):
from math import log

n = int(raw_input())
x = map(int, raw_input().split())
m, k = map(int, raw_input().split())
a = map(lambda x:int(x) - 2, raw_input().split())

logk = log(k, 2)
dy = [x[i + 1] - x[i] for i in xrange(n - 1)]
swap = [range(n - 1) for _ in xrange(int(logk + 1))]

for i in xrange(m):
    swap[0][a[i]], swap[0][a[i] + 1] = swap[0][a[i] + 1], swap[0][a[i]]

j = 1
while j <= logk:
    for i in xrange(n - 1):
        swap[j][i] = swap[j - 1][swap[j - 1][i]]
    j += 1

last = range(n - 1)
j = 0
while k >> j > 0:
    if (k >> j) & 1 == 1:
        for i in xrange(n - 1):
            last[i] = swap[j][last[i]]
    j += 1

ans = x[0]
print(ans)
for i in xrange(n - 1):
    ans += dy[last[i]]
    print(ans)

Solution (Python):
ii=lambda:map(int,raw_input().split())
n=int(raw_input())
x=ii()
m,k=ii()
a=ii()
y=[x[i+1]-x[i] for i in range(n-1)]
a=[a[i]-2 for i in range(m)]
p=[i for i in range(n-1)]
for i in a:
    p[i],p[i+1]=p[i+1],p[i]
bit=list(reversed(map(int,list(bin(k)[2:]))))
q=[[] for i in range(len(bit))]
ans=[i for i in range(n)]
for i in range(len(bit)):
    if i==0: q[0]=[p[j] for j in range(n-1)]
    else: q[i]=[q[i-1][q[i-1][j]] for j in range(n-1)]
    if bit[i]:ans=[q[i][ans[j]] for j in range(n-1)]
w=x[0]
print w
for i in range(n-1):
    w+=y[ans[i]]
    print w