題目鏈接：點擊查看
題目大意：給出一個長度為 n 的排列，初始時為 1 , 2 , 3 ... n - 1 , n，現在有 m 次操作，每次操作表示為 ( k , x ) ，即進行 x 次 k-約瑟夫變換，問最終排列
題目分析：對于每一次的 k-約瑟夫變換，都可以視為一次置換群的結合操作，所以我們首先需要求出這個置換群是什么，假設上一次被取出來的數字是第 pos 個（ 初始時為 1 ），此時環內還剩下 cnt 個數字，則下一次需要被選出的數字是剩下數字的第 ( pos - 1 + k - 1 ) % cnt + 1 個，這個操作可以利用線段樹上二分實現，時間復雜度為 nlogn
在求出置換群后，置換 x 次相當于置換群的 x 次冪，這個直接 O( n ) 去實現就好了，?？投沧鲞^一個類似的題，也是需要求置換群的冪
總的時間復雜度為 nmlogn
代碼：
?
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
#include<unordered_map>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e5+100;int ans[N],temp[N],p[N],n,m;bool vis[N];struct Node
{int l,r,sum;
}tree[N<<2];void build(int k,int l,int r)
{tree[k].l=l;tree[k].r=r;if(l==r){tree[k].sum=1;return;}int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;
}int query(int k,int pos)//找第pos大的數
{tree[k].sum--;if(tree[k].l==tree[k].r)return tree[k].l;if(tree[k<<1].sum>=pos)return query(k<<1,pos);elsereturn query(k<<1|1,pos-tree[k<<1].sum);
}void solve(int t)//O(n)實現置換群p的t次冪
{memset(vis,false,n+5);for(int i=1;i<=n;i++){if(vis[i])continue;vector<int>circle;int pos=i;while(!vis[pos]){circle.push_back(pos);vis[pos]=true;pos=p[pos];}int sz=circle.size();for(int i=0;i<sz;i++)temp[circle[i]]=ans[circle[(i+t)%sz]];}for(int i=1;i<=n;i++)ans[i]=temp[i];
}int main()
{
#ifndef ONLINE_JUDGE
// freopen("data.in.txt","r",stdin);
// freopen("data.out.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)ans[i]=i;while(m--){build(1,1,n);int x,k,pos=1,cnt=n;scanf("%d%d",&k,&x);for(int i=1;i<=n;i++)//將k-約瑟夫變換轉換為置換群{pos=(pos-1+k-1)%cnt+1;p[i]=query(1,pos);cnt--;}solve(x);}for(int i=1;i<=n;i++)printf("%d ",ans[i]);return 0;
}
?
總結
以上是生活随笔為你收集整理的牛客多校6 - Josephus Transform(线段树求k-约瑟夫环+置换群的幂)的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
