UVALive - 3510 Pixel Shuffle (置换)

题目链接

有一个n*n的图像和7种置换，以及一个置换序列，求将这个序列重复做几次能得到原图像。

将这些置换序列乘起来可得到一个最终置换，这个置换所有循环节的长度的lcm即为答案。

注意置换是从右往左进行的，开始没仔细读题，debug到崩溃~~

 #include<bits/stdc++.h>

 using namespace std;

 typedef unsigned long long ll;

 const int N=+;

 typedef vector<int> Per;

 Per operator*(const Per& a,const Per& b) {

     Per c(a.size());

     for(int i=; i<c.size(); ++i)c[i]=b[a[i]];

     return c;

 }

 Per inv(const Per& a) {

     Per c(a.size());

     for(int i=; i<c.size(); ++i)c[a[i]]=i;

     return c;

 }

 Per a[][];

 int n,k,ka;

 int f(int i,int j) {return i*n+j;}

 string line;

 int vis[N*N];

 ll lcm(ll a,ll b) {return a/__gcd(a,b)*b;}

 int main() {

     int T;

     for(scanf("%d",&T); T--;) {

         !ka?++ka:puts("");

         scanf("%d ",&n);

         for(int i=; i<; ++i)a[i][].resize(n*n);

         for(int i=; i<n; ++i)

             for(int j=; j<n; ++j) {

                 a[][][f(i,j)]=f(i,j);

                 a[][][f(i,j)]=f(n--j,i);

                 a[][][f(i,j)]=f(i,n--j);

                 a[][][f(i,j)]=i<n/?f(i,j):f(i,n--j);

                 a[][][f(i,j)]=i<n/?f(i,j):f(n--i+n/,j);

                 a[][][f(i,j)]=i&?f(i/+n/,j):f(i/,j);

                 a[][][f(i,j)]=i&?f(i-(j&^),j/+n/):f(i+(j&),j/);

             }

         for(int i=; i<; ++i)a[i][]=inv(a[i][]);

         swap(a[][],a[][]);

         Per p=a[][];

         getline(cin,line);

         stringstream ss(line);

         string s;

         while(ss>>s) {

             int t=;

             if(s.back()=='-')t=,s.pop_back();

             if(s=="id")p=a[][t]*p;

             else if(s=="rot")p=a[][t]*p;

             else if(s=="sym")p=a[][t]*p;

             else if(s=="bhsym")p=a[][t]*p;

             else if(s=="bvsym")p=a[][t]*p;

             else if(s=="div")p=a[][t]*p;

             else if(s=="mix")p=a[][t]*p;

         }

         memset(vis,,sizeof vis);

         ll ans=;

         for(int i=; i<p.size(); ++i)if(!vis[i]) {

                 ll cnt=;

                 vis[i]=;

                 for(int j=p[i]; j!=i; vis[j]=,j=p[j])++cnt;

                 ans=lcm(ans,cnt);

             }

         printf("%lld\n",ans);

     }

     return ;

 }