Codeforces #24 C Sequence of Points

題意是﹕給出二維點M0, A0...A(N-1), 任意Mi (i > 0) 都使得A_((i-1)%N)為Mi及M(i-1)的中點。
問Mj是甚麼，N<=10^5保証是奇數，j <= 10^18。

驟看很複雜，但不妨先重溫中點公式﹕

定理（中點公式）﹕對於兩點A及B，C是兩點的中點若且僅若C=(A+B)/2，這公式皆把三點都看成向量計算。

因此，題意說的是知道(Mi+M(i-1))/2=A((i-1)%N)，問Mj是甚麼。
把公式重寫，得出 Mi = 2A((i-1)%N) - M(i-1) 這道遞迴式。
因為取模使式子變得難分析，故先取i < N的情況。依推導，可得﹕
M0 = M0
M1 = 2A0 - M0
M2 = 2A1 - M1 = 2A1 - 2A0 + M0
M3 = 2A2 - M2 = 2A2 - 2A1 + 2A0 - M0
.
.
M(N-1) = 2A(N-2) - M0 = 2A(N-2) - 2A(N-1) + ... - 2A0 + M0
MN = 2A(N-1) - M(N-1) = 2A(N-1) - 2A(N-2) + ... + 2A0 - M0
好像沒有甚麼有用的資訊。但加入取模的情況下就有點頭緒了，且看M(N+1)﹕
M(N+1) = 2A(N%N) - MN = 2A0 - 2A(N-1) + 2A(N-2) - ... - 2A0 + M0 = - 2A(N-1) + 2A(N-2) - ... + M0

A0被抵銷了。同一道理，A0和A1也會在M(N+2)被抵銷。因此可以推導出A0, A1, ... A(N-1) 會在M(N+N)被抵銷。因此可知M(2N)數值上是和M0一樣，但會不會是-M0呢？留意上述推導的式子中，只有奇數項才會出現-M0，而2N是偶數，因此M(2N) = M0。

因此可以肯定M0...M(2N-1)是數列的循環部分，所以只需預計算M0...M(2N-1)，然後直接取M(K%2N)即可。