链接：https://vjudge.net/problem/UVA-1156
题目大意：给定一个n*n的像素图，有若干种操作将图做一个映射，给定若干映射，求至少反复做这些映射多少次，能得到原图。
分析：将图看做一个n^2*1的向量，每种操作就是一种置换，求出给的置换的乘积M，然后将M分解为正交的若干置换的乘积，答案就是这些置换的长度的最小公约数。注意给的映射是从后面的开始执行。。。
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<string> 5 using namespace std; 6 typedef long long ll; 7 const int maxn=(1<<20)+5; 8 int rot[maxn],sym[maxn],bhs[maxn],bvs[maxn],Div[maxn],mix[maxn]; 9 int n; 10 void CalT(){ 11 for(int i=0;i<n*n;i++){ 12 int x=i/n,y=i%n; 13 rot[i]=y*n+n-x-1; 14 } 15 for(int i=0;i<n*n;i++){ 16 int x=i/n,y=i%n; 17 sym[i]=x*n+n-1-y; 18 } 19 for(int i=0;i<n*n/2;i++)bhs[i]=i; 20 for(int i=n*n/2;i<n*n;i++){ 21 int x=i/n,y=i%n; 22 bhs[i]=x*n+n-1-y; 23 } 24 for(int i=0;i<n*n/2;i++)bvs[i]=i; 25 for(int i=n*n/2;i<n*n;i++){ 26 int x=i/n,y=i%n; 27 bvs[i]=(n-1-x+n/2)*n+y; 28 } 29 for(int i=0;i<n*n/2;i++){ 30 int x=i/n,y=i%n; 31 Div[i]=2*x*n+y; 32 } 33 for(int i=n*n/2;i<n*n;i++){ 34 int x=i/n,y=i%n; 35 Div[i]=(2*(x-n/2)+1)*n+y; 36 } 37 for(int x=0;x<n;x+=2){ 38 for(int y=0;y<n/2;y++){ 39 mix[x*n+2*y]=x*n+y; 40 mix[x*n+2*y+1]=(x+1)*n+y; 41 } 42 } 43 for(int x=1;x<n;x+=2){ 44 for(int y=0;y<n/2;y++){ 45 mix[x*n+2*y]=(x-1)*n+y+n/2; 46 mix[x*n+2*y+1]=x*n+y+n/2; 47 } 48 } 49 } 50 char p[500]; 51 int M[maxn],M0[maxn]; 52 void Copy(int *a,int *b,int n){ 53 for(int i=0;i<n;i++)a[i]=b[i]; 54 } 55 void Mu(int *a){ 56 for(int i=0;i<n*n;i++){ 57 M0[i]=M[a[i]]; 58 } 59 Copy(M,M0,n*n); 60 } 61 void Mu_(int *a){ 62 for(int i=0;i<n*n;i++){ 63 M0[a[i]]=M[i]; 64 } 65 Copy(M,M0,n*n); 66 } 67 //void Print(){ 68 // for(int i=0;i<n;i++){ 69 // for(int j=0;j<n;j++){ 70 // printf("%4d",M[i*n+j]); 71 // } 72 // cout<<endl; 73 // } 74 // cout<<"*******"<<endl; 75 //} 76 void GetM(){ 77 for(int i=0;i<n*n;i++)M[i]=i; 78 int len=strlen(p); 79 int i=len-1,j=len-1; 80 while(i>=0){ 81 while(i>=0&&p[i]!=' ')i--; 82 switch(p[i+1]){ 83 case 'r': 84 if(p[j]=='-')Mu_(rot); 85 else Mu(rot);break; 86 case 's': 87 if(p[j]=='-')Mu_(sym); 88 else Mu(sym);break; 89 case 'b': 90 if(p[i+2]=='h'){ 91 if(p[j]=='-')Mu_(bhs); 92 else Mu(bhs); 93 }else{ 94 if(p[j]=='-')Mu_(bvs); 95 else Mu(bvs); 96 }break; 97 case 'd': 98 if(p[j]=='-')Mu_(Div); 99 else Mu(Div);break; 100 case 'm': 101 if(p[j]=='-')Mu_(mix); 102 else Mu(mix);break; 103 default:break; 104 } 105 // Print(); 106 j=--i; 107 } 108 } 109 int gcd(int a,int b){ 110 return a==0?b:gcd(b%a,a); 111 } 112 int lcm(int a,int b){ 113 return (ll)a*b/gcd(a,b); 114 } 115 bool vis[maxn]; 116 int Getlen(int u){ 117 vis[u]=true; 118 int next=M[u],cnt=1; 119 while(next!=u){ 120 vis[next]=true; 121 next=M[next]; 122 cnt++; 123 } 124 return cnt; 125 } 126 int solve(){ 127 int m=1; 128 memset(vis,0,sizeof(vis)); 129 for(int i=0;i<n*n;i++){ 130 if(vis[i])continue; 131 int q=Getlen(i); 132 m=lcm(m,q); 133 } 134 return m; 135 } 136 //void test(){ 137 // cin>>n; 138 // CalT(); 139 // for(int i=0;i<n;i++){ 140 // for(int j=0;j<n;j++){ 141 // cin>>M[i*n+j]; 142 // } 143 // } 144 // Print(); 145 // 146 // cout<<"rot"<<endl; 147 // Mu(rot); 148 // Print(); 149 // Mu_(rot); 150 // Print(); 151 // 152 // cout<<"sym"<<endl; 153 // Mu(sym); 154 // Print(); 155 // Mu_(sym); 156 // Print(); 157 // 158 // cout<<"bhs"<<endl; 159 // Mu(bhs); 160 // Print(); 161 // Mu_(bhs); 162 // Print(); 163 // 164 // cout<<"bvs"<<endl; 165 // Mu(bvs); 166 // Print(); 167 // Mu_(bvs); 168 // Print(); 169 // 170 // cout<<"div"<<endl; 171 // Mu(Div); 172 // Print(); 173 // Mu_(Div); 174 // Print(); 175 // 176 // cout<<"mix"<<endl; 177 // Mu(mix); 178 // Print(); 179 // Mu_(mix); 180 // Print(); 181 //} 182 int main(){ 183 // freopen("e:\in.txt","r",stdin); 184 // test(); 185 int T; 186 scanf("%d",&T); 187 for(int kase=0;kase<T;kase++){ 188 if(kase)printf(" "); 189 scanf("%d ",&n); 190 cin.getline(p,500); 191 CalT(); 192 GetM(); 193 printf("%d ",solve()); 194 } 195 return 0; 196 }