https://ac.nowcoder.com/acm/contest/5671/J
题意：
初始有一个1-n的排列，对这个排列进行m次操作，每次操作对排列进行x次k-约瑟夫置换，问m次操作后的序列是什么。
k-约瑟夫置换：n个数围成一个圈，从第1个开始，数到第k个，将这个数字去掉，操作n次直至圈为空。数字去掉的顺序就是对该排列进行1次k-约瑟夫置换后的序列。
一个置换可以定义为一个函数的复合
记f={a1，a2，a3，……an }表示数1-n的一个置换，即 i-->ai，ai<=n
对于某一个操作来说，它的x次k-约瑟夫置换对每一个数进行的置换都是相同的。
比如：7个数进行5次4约瑟夫置换
1 2 3 4 5 6 7
一 4 1 6 5 7 3 2
二 5 4 3 7 2 6 1
三 7 5 6 2 1 3 4
四 2 7 3 1 4 6 5
五 1 2 6 4 5 3 7
其f={4,1,6,5,7,3,2}
置换（函数复合）乘法满足乘法结合律
所以只需要得到第一次的置换结果，对于x次同样的置换，用快速幂的方式完成即可
数学渣渣表示记住结论走人
第一次的置换结果就是模拟约瑟夫问题
假设上一个去掉的数字是在剩余的数中的第x个，去掉之后剩余m个数字，
那么这一次选出的数字就是这m个数字中的第（x-1+k）%m 个，若结果为0就是第m个
上式等价于（x-1+k-1）%m+1
如何得到剩余m个数字中的第y个数字？
利用线段树或者树状数组二分
初始每个位置都是1，表示这个数字还没有去掉
当去掉一个数字时，它的位置减去1
每次二分一个位置，查询前缀和，直到前缀和为y
然后记第i种操作的置换为Pi，那么所有的置换可以表示为 （P1^x1）（P2^x2）(P3^x3)……（Pm^xm）
即暴力的求法是 P1*P1……*P1*P2*P2*P2……*Pm*Pm……*Pm (x1个P1，x2个P2……xm个Pm
快速幂的方式是利用结合律，先将所有的P1算完，再算所有的P2，……最后将m个结果相乘得到最终结果
相乘的时候注意顺序
#include<cstdio>
#include<cstring>
using namespace std;
#define N 100001
#define lowbit(x) x&-x
int a[N],tmp[N],to[N],ans[N];
int n,c[N];
void add(int x,int y)
{
while(x<=n)
{
c[x]+=y;
x+=lowbit(x);
}
}
int query(int x)
{
int s=0;
while(x)
{
s+=c[x];
x-=lowbit(x);
}
return s;
}
void find_one(int k)
{
int last=1,now,l,r,mid,pos;
for(int i=1;i<=n;++i) c[i]=0;
for(int j=1;j<=n;++j) add(j,1);
for(int j=1;j<=n;++j)
{
pos=(last-1+k-1)%(n-j+1)+1;
l=1;
r=n;
while(l<=r)
{
mid=l+r>>1;
if(query(mid)>=pos) now=mid,r=mid-1;
else l=mid+1;
}
a[j]=now;
last=query(now);
add(now,-1);
}
}
void mul(int x)
{
for(int i=1;i<=n;++i) to[i]=i;
while(x)
{
if(x&1)
{
for(int i=1;i<=n;++i) tmp[i]=to[a[i]];
for(int i=1;i<=n;++i) to[i]=tmp[i];
}
x>>=1;
for(int i=1;i<=n;++i) tmp[i]=a[a[i]];
for(int i=1;i<=n;++i) a[i]=tmp[i];
}
for(int i=1;i<=n;++i) tmp[i]=ans[to[i]];
for(int i=1;i<=n;++i) ans[i]=tmp[i];
}
int main()
{
int m,k,x;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) ans[i]=i;
for(int i=1;i<=m;++i)
{
scanf("%d%d",&k,&x);
find_one(k);
mul(x);
}
for(int i=1;i<=n;++i) printf("%d ",ans[i]);
}