P6148 [USACO20FEB]Swapity Swapity Swap S

思路

USACO思维题
引入置换概念，实现类似快速幂
预处理m次翻转后的对应关系，k用矩阵快速幂加速
stl函数reverse，头文件algorithm，实现数列翻转

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#define maxn 100005
using namespace std;
int n,m,k;
struct fdfdfd{int t[maxn];}e,a;
fdfdfd mul(fdfdfd a,fdfdfd b)
{
	fdfdfd c;
	for(int i=1;i<=n;++i) c.t[i]=a.t[b.t[i]];
	return c;
}
void qpow(int k)
{
	while(k)
	{
		if(k&1) a=mul(a,e);
		k>>=1; e=mul(e,e);
	}
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;++i) e.t[i]=a.t[i]=i;
	for(int i=1,l,r;i<=m;++i) scanf("%d%d",&l,&r),reverse(e.t+l,e.t+r+1);
	qpow(k);
	for(int i=1;i<=n;++i) printf("%d
",a.t[i]);
	return 0;
}