记录编号	417044	评测结果	AAAAAAAAAA
题目名称	[UVa 1156] 像素混合	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	1.009 s
提交时间	2017-06-23 21:18:02	内存使用	17.33 MiB

#include<cstdio>
const int N=1<<10|1;
int T,n,m,id[N][N],a[N*N],cnt;
//a[i]为变换之后数值为i的位置 
void get_inv(){
	static int b[N*N];
	for (int i=0;i<cnt;i++) b[a[i]]=i;
	for (int i=0;i<cnt;i++) a[i]=b[i];
}
void get_id(){
	for (int i=0;i<cnt;i++) a[i]=i;
}
void get_rot(){
	for (int i=0;i<n;i++)
	for (int j=0;j<n;j++)
		a[id[i][j]]=id[j][n-i-1];
}
void get_sym(){
	for (int i=0;i<n;i++)
	for (int j=0;j<n;j++)
		a[id[i][j]]=id[i][n-j-1];
}
void get_bhsym(){
	for (int i=0;i<n;i++)
	for (int j=0;j<n;j++)
		a[id[i][j]]=(i<m?id[i][j]:id[i][n-j-1]);
}
void get_bvsym(){
	for (int i=0;i<n;i++)
	for (int j=0;j<n;j++)
		a[id[i][j]]=(i<m?id[i][j]:id[n+m-i-1][j]);
}
void get_div(){
	for (int i=0;i<n;i++)
	for (int j=0;j<n;j++)
		a[id[(i>>1)+(i&1?m:0)][j]]=id[i][j];
}
void get_mix(){
	for (int i=0;i<m;i++)
	for (int j=0;j<n;j++){
		a[id[i<<1][j]]=id[i<<1|(j&1)][j>>1];
		a[id[i<<1|1][j]]=id[i<<1|(j&1)][(j>>1)+m];  
	}
}
int ans[N*N];
void multify(){
	for (int i=0;i<cnt;i++) ans[i]=a[ans[i]];
}
bool vis[N*N];
char s[N];
int gcd(int x,int y){return y?gcd(y,x%y):x;}
int main()
{
	freopen("pixelshuffle.in","r",stdin);
	freopen("pixelshuffle.out","w",stdout);
	scanf("%d",&T);
	while (T--){
		scanf("%d",&n);
		gets(s);
		m=n>>1;cnt=0;
		for (int i=0;i<n;i++)
		for (int j=0;j<n;j++)
			id[i][j]=cnt++;
		for (int i=0;i<cnt;i++) ans[i]=i;
		gets(s);
		for (int p=0;;){
			while (s[p]&&(s[p]>'z'||s[p]<'a')) p++;
			if (!s[p]) break;
			if (s[p]=='i') get_id();else
			if (s[p]=='r') get_rot();else
			if (s[p]=='s') get_sym();else
			if (s[p]=='d') get_div();else
			if (s[p]=='m') get_mix();else
			if (s[p+1]=='h') get_bhsym();
				else get_bvsym();
			while (s[p]&&s[p]!='-'&&s[p]!=' ') p++;
			if (s[p]=='-') get_inv(),p++;
			multify();
		}
		for (int i=0;i<cnt;i++) vis[i]=0;
		int Ans=1;
		for (int i=0;i<cnt;i++)
		if (!vis[i]){
			int size=0;
			for (int x=i;!vis[x];x=ans[x]) size++,vis[x]=1;
			Ans=Ans/gcd(Ans,size)*size;
		}
		printf("%d\n\n",Ans);
	}
	return 0;
}