题意分析

本题要求计算一个由多个基本变换组成的复合变换φ的最小周期m，即满足φ^m为恒等变换的最小正整数m。每个基本变换可以是正向或反向操作，复合变换按从右到左的顺序应用（如k1∘k2表示先应用k2，再应用k1）。

关键思路

1. 基本变换的分解与建模
   将每个基本变换视为对图像像素位置的置换，并计算其置换的循环分解。每个循环的长度为l，则该变换的周期为各循环长度的最小公倍数（LCM）。

   • 对于复合变换φ，其置换是各基本变换置换的复合（从右到左），需将每个基本变换的置换逆序复合（如φ = k1∘k2对应置换p1·p2，其中p2是k2的置换，p1是k1的置换）。

2. 置换的复合与循环分解

   • 每个基本变换（如旋转、对称、分割合并）可分解为对图像子块的置换操作。对于n×n的图像（n为偶数），可递归分解为4个(n/2)×(n/2)的子块（如左上、右上、左下、右下，记为A、B、C、D），每个变换作用于子块的位置和子块内部。
   • 定义每个变换对子块位置的置换和对子块内部的操作（如旋转、对称等），递归处理子块直到1×1像素（无需变换）。

3. 周期计算

   • 对于每个子块位置的置换和子块内部的变换，分别计算其循环周期，最终周期为所有层次上的周期的LCM。

基本变换的置换定义

以下是各基本变换对4个子块的位置置换和子块内部操作（正向变换）：

注：

• div和mix用于控制递归分解的层次，div表示当前子块需继续分解为4个子块，mix表示停止分解（即当前子块为最小单元，如1×1像素）。
• 逆变换的子块位置置换为正向置换的逆置换，子块内部操作也取逆（如rot-的子块旋转为顺时针90°，是rot的逆操作）。

递归求解周期

1. 终止条件：当子块大小为1×1时，无需变换，周期为1。
2. 递归处理：
   • 对于当前子块大小s×s（s>1），根据变换序列判断是否需要分解（由div和mix控制）。若当前变换包含div，则递归分解为4个子块；若包含mix，则停止分解，视为原子操作。
   • 对每个基本变换，计算其对当前子块的位置置换和内部变换，复合所有变换后得到最终的置换。
   • 对位置置换和内部变换分别计算循环周期，取LCM作为当前子块的周期。
3. 复合变换的处理：按从右到左的顺序应用每个基本变换的置换（即先处理最后一个变换，再处理前一个变换）。

代码实现步骤

1. 解析变换序列：将输入的变换序列转换为正向或反向操作的列表，如rot-转换为rot的逆变换。
2. 定义基本变换的置换和逆置换：对每个变换，存储其子块位置置换和内部操作的逆操作。
3. 递归计算周期：
   • 函数compute_cycle(s, transforms)计算大小为s×s的子块在给定变换序列下的周期。
   • 若s=1，返回1。
   • 否则，根据变换序列中的div和mix判断是否需要分解。若需要分解（当前变换包含div），则递归计算4个子块的周期，否则视为原子块，计算位置置换和内部变换的周期。
4. 计算置换的循环周期：对位置置换和内部变换的置换分别进行循环分解，计算各循环长度的LCM。

#include <iostream>
#include <cstdio>
#include <cstring>

#define PLA(x,y) PLAS[(x)][(y)]

using namespace std;

char input[100000];
int T,n,cnt;
int row[100000];
int to[1300000];
bool vis[1300000];
int PLAS[2000][2000];
int nxt[1300000];

int gcd(int x,int y){
    return y==0?x:gcd(y,x%y);
}

void work(int x){
    switch(x){
        case 9:
            for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                    nxt[PLA(i,j)]=to[PLA(j,n-i-1)];
            break;
        case 3:
            for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                    nxt[PLA(i,j)]=to[PLA(i,n-j-1)];
            break;
        case 4:
            for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                    if(i>=n/2)nxt[PLA(i,j)]=to[PLA(i,n-j-1)];
            break;
        case 5:
            for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                    if(i>=n/2)nxt[PLA(i,j)]=to[PLA(n/2+n-1-i,j)];
            break;
        case 7:
            for(int i=0;i<n;i++)
                for(int j=0;j<n;j++){
                    if(!((i)&1))nxt[PLA(i,j)]=to[PLA(i+((j)&1),(j)/2)];
                    else nxt[PLA(i,j)]=to[PLA(i+((j)&1)-1,(j)/2+n/2)];
                }
            break;
        case 2:
            for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                    nxt[PLA(i,j)]=to[PLA(n-j-1,i)];
            break;
        case 6:
            for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                    if(i<n/2)nxt[PLA(i,j)]=to[PLA((i)*2,j)];
                    else nxt[PLA(i,j)]=to[PLA(2*(i-n/2)+1,j)];
            break;
        case 13:
            for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                    if(!((i)&1))nxt[PLA(i,j)]=to[PLA(i/2,j)];
                    else nxt[PLA(i,j)]=to[PLA(i/2+n/2,j)];
            break;
        case 14:
            for(int i=0;i<n;i++)
                for(int j=0;j<n;j++){
                    if(j<n/2){
                        if(!((i)&1))nxt[PLA(i,j)]=to[PLA(i,(j)*2)];
                        else nxt[PLA(i,j)]=to[PLA(i-1,(j)*2+1)];
                    }
                    else{
                        if(!((i)&1))nxt[PLA(i,j)]=to[PLA(i+1,(j-n/2)*2)];
                        else nxt[PLA(i,j)]=to[PLA(i,(j-n/2)*2+1)];
                    }
                }
            break;
        default:break;
    }
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            to[PLA(i,j)]=nxt[PLA(i,j)];
}

int main(){

    scanf("%d",&n);gets(input);if((input[0]<'a'||input[0]>'z')&&(input[0]<'A'||input[0]>'Z'))gets(input);

    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)PLAS[i][j]=((i)*n+(j)+1);

    int l=strlen(input);cnt=0;

    int end=PLA(n-1,n-1);
    for(int i=1;i<=end;i++)to[i]=nxt[i]=i;

    for(int i=0;i<=l;i++){
        if(input[i]==' '||i==l){
            switch(input[i-1]){
                case 'd':continue;
                case 't':row[++cnt]=2;break;
                case 'v':row[++cnt]=6;break;
                case 'x':row[++cnt]=7;break;
                case 'm':
                    if(i>3&&input[i-4]=='h')row[++cnt]=4;
                    else if(i>3&&input[i-4]=='v')row[++cnt]=5;
                    else row[++cnt]=3;
                    break;
                case '-':
                    switch(input[i-2]){
                        case 'd':continue;
                        case 't':row[++cnt]=9;break;
                        case 'v':row[++cnt]=13;break;
                        case 'x':row[++cnt]=14;break;
                        case 'm':
                            if(i>4&&input[i-5]=='h')row[++cnt]=4;
                            else if(i>4&&input[i-5]=='v')row[++cnt]=5;
                            else row[++cnt]=3;
                            break;
                        default:break;
                    }
                    break;
                default:break;
            }
        }
    }

    for(int i=cnt;i>=1;i--)work(row[i]);

    int ans=1;
    for(int i=1;i<=end;i++)if(!vis[i]){
        int j=i,tot=0;
        do{
            vis[j]=true;
            tot++;
            j=to[j];
        }while(i!=j);   
        ans=ans/gcd(ans,tot)*tot;
    }
    printf("%d",ans);

    return 0;
}