记录编号	85990	评测结果	AAAAAAAAAA
题目名称	[UVa 1156] 像素混合	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.742 s
提交时间	2014-01-18 22:37:17	内存使用	9.31 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<iomanip>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
const int SIZEL=1024*1024+10;//N^2
//为方便起见,本程序中的下标从0开始
int n;
#define hash(i,j) ((i)*n+(j))
void transform(int a[SIZEL],int b[SIZEL],const char* opt){
	int i=0,j,x,y;
	bool type=1;
	if(opt[strlen(opt)-1]=='-') type=0;
	for(x=0;x<n;x++){
		for(y=0;y<n;y++){
			j=i;//没有这一条会T的很惨.....
			if(opt[0]=='r') j=hash(n-1-y,x);//rot
			else if(opt[0]=='s') j=hash(x,n-1-y);//sym
			else if(opt[0]=='b'&&opt[1]=='h') j=(x<n/2?hash(x,y):hash(x,n-1-y));//bhsym
			else if(opt[0]=='b'&&opt[1]=='v') j=(x<n/2?hash(x,y):hash(n/2*3-1-x,y));//bvsym
			else if(opt[0]=='d') j=(x&1?hash(x/2+n/2,y):hash(x/2,y));//div
			else if(opt[0]=='m') j=(y<n/2?hash(x&(~1),2*y+(x&1)):hash(x|1,2*y-n+(x&1)));//mix
			if(type) b[j]=a[i];
			else b[i]=a[j];
			i++;
		}
	}
}
ll gcd(ll a,ll b){
	return !b?a:gcd(b,a%b);
}
ll lcm(ll a,ll b){
	return a/gcd(a,b)*b;
}
bool visit[SIZEL]={0};
ll solve(int a[]){//a是一个置换
	memset(visit,0,sizeof(visit));
	int i,j,tot;
	ll ans=1;
	for(i=0;i<n*n;i++){
		if(visit[i]) continue;
		j=i,tot=0;
		do{
			j=a[j];
			visit[j]=true;
			tot++;
		}while(j!=i);
		ans=lcm(ans,tot);
	}
	return ans;
}
int ori[SIZEL]={0},aft[SIZEL]={0};
vector<string> opl;
void work(void){
	int T,n1,i,j;
	scanf("%d%d",&T,&n1);
	string op;
	while(T--){
		opl.clear();
		n=n1;
		for(i=0;i<n*n;i++) ori[i]=i;
		i=0;
		while(true){
			if(!(cin>>op)) break;
			if(isdigit(op[0])){
				sscanf(op.c_str(),"%d",&n1);
				break;
			}
			opl.push_back(op);
		}
		for(i=opl.size()-1;i>=0;i--){
			transform(ori,aft,opl[i].c_str());
			for(j=0;j<n*n;j++) ori[j]=aft[j];
		}
		printf("%lld\n",solve(aft));
		if(T) printf("\n");
	}
}
int main(){
	freopen("pixelshuffle.in","r",stdin);
	freopen("pixelshuffle.out","w",stdout);
	work();
	return 0;
}