I纸牌 胡搞

Stratoes:首先假设k ≤ n – 1，那么我们可以这么做：将每个牌中间留一个空位，每次把牌堆顶的第一张牌放到合适的空位上，可以证明这么做是可行的。因此我们维护一个数组和一个指向牌堆顶的指针，一开始将第i张牌放在2*i-1的位置。第j次操作时将牌堆顶的牌放在(j + 1) * 2的位置即可。这样我们就在O(n)时间内完成了要求的操作。
当k很大时，假设n-1次后的编号为p[i]，则2(n – 1)次后的编号为p[p[i]], 以此类推。令x = ⌊k / n⌋，则我们通过将排列p的拆分成若干个循环，就可以通过循环节的长度求得p^x，即k – k % (n – 1)次后的编号，剩下k % (n – 1)次直接模拟就好。总的时间复杂度为O(n)。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 10;
typedef long long ll;
int n;
ll k;
int p[maxn], tmp[maxn];
bool vis[maxn];
void getNext(int * a, int k)
{
    memset(tmp, 0, sizeof tmp);
    for(int i = 1; i <= n; ++i) tmp[(i << 1) - 1] = a[i];
    int cur = 1;
    for(int i = 1; i <= k; ++i)
    {
        while(!tmp[cur]) ++cur;
        swap(tmp[cur], tmp[(i + 1) << 1]);
    }
    int tot = 0;
    for(int i = 1; i <= 2 * n; ++i)
        if(tmp[i])
            a[++tot] = tmp[i];
}
void getCycle(int * a, ll k)
{
    for(int i = 1; i <= n; ++i)
        if(!vis[i])
        {
            int cur = i, tot = 0;
            while(!vis[cur])
            {
                tmp[++tot] = cur;
                vis[cur] = 1;
                cur = a[cur];
            }
            tmp[0] = tmp[tot];
            int shift = k % tot;
            for(int j = 0; j < tot; ++j)
                a[tmp[j]] = tmp[(j + shift) % tot];
        }   
}
int main()
{
    cin >> n >> k;
    for(int i = 1; i <= n; ++i) p[i] = i; 
    getNext(p, n - 1);
    getCycle(p, k / (n - 1));
    getNext(p, k % (n - 1));
    for(int i = 1; i <= n; ++i) cout << p[i] << ' ';
    cout << '\n';
    return 0;
}

Dzerzhinski: k – k % (n – 1)部分也可以快速幂计算。整体复杂度是O(n log(k/n))

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int arr[1001000];
int temp[2002000];
int powans[1001000];
int n;
ll k;
void step(int pre[],int step){
    for(int i=0;i<n;i++){
        temp[i*2]=pre[i];
        temp[i*2+1]=0;
    }
    int now = 0;
    for(int i=0;i<step;i++){
        while(temp[now]==0)now++;
        swap(temp[now],temp[(i+1)*2+1]);
    }
    now=0;
    for(int i=0;i<2*n;i++){
        if(temp[i])pre[now++]=temp[i];
    }
}
void mul(int a[],int b[]){
    for(int i=0;i<n;i++){
        temp[i]=a[b[i]-1];
    }
    for(int i=0;i<n;i++)a[i]=temp[i];

}

void powmod(int a[],ll p){
    for(int i=0;i<n;i++)powans[i]=i+1;
    while(p){
        if(p%2){
            mul(powans,a);
        }
        p/=2;
        mul(a,a);
    }
}

int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++)arr[i]=i+1;
    step(arr,n-1);
    powmod(arr,k/(n-1));
    step(powans,k%(n-1));

    for(int i=0;i<n;i++){
         cout<<powans[i]<<" ";
    }
    cout<<endl;
    return 0;
}