C++14(g++5.4) 解法, 执行用时: 345ms, 内存消耗: 20836K, 提交时间: 2020-05-10 16:08:07

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int a[1000010];
int b[1000010];
int c[1000010];
int d[1000010];
int calcu(int x,int k){
  int cnt=0,now=x;k++;
  if(x!=1){
    if(k<=x-1)return x;
    cnt=x-1;now=x;
  }
  while(cnt<k){
    cnt+=now,now=cnt;
    if(cnt==k) return now;
    if(cnt>k) return cnt-k;
  }
}
int main(){
  ios::sync_with_stdio(0);cin.tie(0);
  // while(1){int a,b;cin>>a>>b;cout<<calcu(a,b)<<endl;}
  int n;ll k;cin>>n>>k;
  for(int i=1;i<=n;i++)a[i]=calcu(i,n-1),d[i]=calcu(i,k%(n-1));

  // for(int i=1;i<=n;i++)cout<<a[i]<<" ";cout<<endl;
  // for(int i=1;i<=n;i++)cout<<d[i]<<" ";cout<<endl;

  ll cnt=k/(n-1);
  for(int i=1;i<=n;i++)c[i]=i;
  while(cnt){
    if(cnt&1){
      for(int i=1;i<=n;i++)b[i]=a[c[i]];
      for(int i=1;i<=n;i++)c[i]=b[i];
    }
    for(int i=1;i<=n;i++)b[i]=a[a[i]];
    for(int i=1;i<=n;i++)a[i]=b[i];
    cnt>>=1;
  }
  for(int i=1;i<=n;i++)b[d[c[i]]]=i;
  for(int i=1;i<=n;i++)cout<<b[i]<<" ";cout<<endl;
}

C++11(clang++ 3.9) 解法, 执行用时: 278ms, 内存消耗: 55204K, 提交时间: 2020-05-11 16:42:30

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+50;
int p[maxn],a[maxn],tmp[maxn*2],pos[maxn],bel[maxn],vis[maxn];
vector<int>qun[maxn];
void getQun(int n){ int cnt=0;
	for(int i=1;i<=n;i++){
		if(!vis[i]){ int q=i;cnt++;int nowpo=0;
			while(!vis[q]) qun[cnt].push_back(q),bel[q]=cnt,pos[q]=nowpo++,vis[q]=1,q=p[q];
		}
	}
}int main(){ 
	int n;ll k;scanf("%d%lld",&n,&k);tmp[1]=1;
	for(int i=2;i<=2*n-1;i++){
		if(i%2==0) tmp[i]=i/2+1;else tmp[i]=0;
	}for(int i=1;i<n;i++){
		tmp[i*2+1]=tmp[i];tmp[i]=0;
	}for(int i=n;i<=2*n-1;i++) p[i-n+1]=tmp[i]; getQun(n);
	int x=k%(n-1);k/=(n-1);tmp[1]=qun[1][k%qun[1].size()];
	for(int i=2;i<=2*n-1;i++){ 
		if(i%2==0){
			int t=i/2+1;int sz=qun[bel[t]].size();
			tmp[i]=qun[bel[t]][((ll)pos[t]+k)%sz];
		}else tmp[i]=0;
	}for(int i=1;i<=x;i++){
		tmp[i*2+1]=tmp[i];tmp[i]=0;
	}for(int i=1;i<=2*n-1;i++){
		if(tmp[i]) printf("%d ",tmp[i]);
	}
	
}