[USACO 2013 Gold] The Bessie Shuffle

作法：

這題的關鍵就是發現到，原題的操作其實就等價於：從最頂層的 m 個數開始，每次對這 m 個數做一次排列，然後把當前窗口往下移一格。也就等價於做的排列操作是 p[ i ] - 1 ，其中 p 代表原始的排列。發現這件事之後就不難想到會用到倍增法了。但原題要問的是最後落在第 x 個位置的卡片是誰，首先把他改成從上面數下來第 n+1-x 張（以後就改把這個數叫 x ），並且考慮把整個排列的操作反過來，也就是如果設 q 是 p 的反函數，那麼我們現在要求的東西就會變成「從下到上進行 q 排列並把視窗往上滑動」之後， x 會落到哪個位置。所以我們要倍增的排列其實會是 q[ i ] - 1 。並且注意到，如果 x 在經過了 k 次轉換之後變成 0 了，那麼這時候 x 的位置就確定了（之後的排列不會再動到他），或是當這個視窗跑到最頂端，無法再進行排列的時候， x 的位置也確定了。所以在倍增求答案的時候，首先要求出第一次會影響的 x 的位置的排列是在哪個視窗，並且得到 x 關於這個視窗的相對位置（從下面數上來第幾個），叫他 now 好了，所以接下來，就是對 now 進行倍增的排列。而倍增的過程中我們只要紀錄兩個數字 num 和 k ，前者代表現在還能再做幾次排列操作，後者代表已經做幾次操作了，那麼由第一次操作的位置和 k ，還有最後 now 到達的位置，就可以算出 x 最後的位置了。

和這題類似的還有 CodeForces 484-C Strange Sorting，一樣是作進行某個排列之後滑動視窗的操作。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10 ;
 
int per[31][maxn] ;
main()
{
    freopen("shufflegold.in","r",stdin) ;
    freopen("shufflegold.out","w",stdout) ;
    int m,n,Q ; scanf("%d%d%d",&m,&n,&Q) ;
    for(int i=1;i<=n;i++)
    {
        int x ; scanf("%d",&x) ;
        per[0][n+1-x]=(n+1-i)-1 ;
    }
    for(int i=1;i<31;i++) for(int j=1;j<=n;j++)
        per[i][j]=per[i-1][per[i-1][j]] ;
 
    while(Q--)
    {
        int x ; scanf("%d",&x) ;
        x=m+1-x ;
        int bot=min(m,x+n-1) , k=0 ;
        int now=bot-x+1 ;
 
        for(int i=30 , num=bot-n;i>=0;i--)
            if(num>=(1<<i) && per[i][now])
        {
            now=per[i][now] ;
            k^=(1<<i) ;
            num-=(1<<i) ;
        }
        k++ ; now=per[0][now] ;
        printf("%d\n",bot-k+1-now) ;
    }
}