题解 AT2136【Reverse Grid】

· · 题解

首先可以把翻转看成某种置换。于是事实上本题就是给定矩阵在置换群操作下的轨道大小求解。

但是事实上不需要使用轨道之类高深的群论技巧。具体而言，观察到某个格子中的元素仅可能出现在四个位置中，列出四个位置如下图：

  .  .
  .  .
..A..B..
  .  .
  .  .
..C..D..
  .  .
  .  .

即图中的 ABCD 四个位置，它们在矩阵中的位置是对称的。

然后接着我们可以发现先翻转 AC，再翻转 CD，再翻转 AC，再翻转 CD 后，除了 ACD 三个元素以外其它所有元素的位置都没变，而这三个元素循环了一位。

除了 ACD 间可以这么做以外，ABC，ABD，BCD 都可以被实现。于是把这些操作结合起来写一个程序验证一下，发现这四种操作总共可以组合出 12 种不同的操作。

四个元素的排列总共有 24 种。而我们发现，只要 ABCD 中任两个元素被交换，再结合上述四种操作，都可以得到剩下 12 种操作。

注意到我们可以翻转一行或一列使得其中所有四元组的置换由原本的 12 种变成另 12 种。这意味着我们如果把每个四元组的状态用一个 bit 来表示，则每个四元组翻转与否的状态即可用一个 O(nm) 的二进制数来表示。翻转每行每列的操作就对应了异或关系。

这很明显是一个线性基问题。可以直接解出所有翻转操作对应二进制数构成的集合的秩来解决问题。但是需要注意的是，有时正 12 种和反 12 种操作是等效的。具体而言，除非 ABCD 四个元素都不同，否则正反操作是等效的。于是，对于存在相同元素的位置，直接把它对应的位从二进制数中删去即可。

还有就是当 n,m 为奇数时，正中央的那一行/列的四元组退化了。这时就直接暴力验证一下翻转操作会不会改变矩阵即可。

线性基的秩求解可以用 bitset 优化。

代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,m,res=1;
struct perm{
    int a[4];
    perm(){memset(a,0,sizeof(a));}
    int&operator[](const int&x){return a[x];}
    friend perm operator*(perm&u,perm&v){
        perm w;
        for(int i=0;i<4;i++)w[i]=v[u[i]];
        return w;
    }
    friend bool operator<(const perm&u,const perm&v){
        for(int i=0;i<4;i++)if(u.a[i]!=v.a[i])return u.a[i]<v.a[i];
        return false; 
    }
};
set<perm>s;
char g[210][210];
bool sp[110][110];
bitset<10100>bs[210];
int main(){
    perm p;
    p[0]=1,p[1]=2,p[2]=0,p[3]=3;s.insert(p);
    p[0]=2,p[2]=3,p[3]=0,p[1]=1;s.insert(p);
    p[0]=1,p[1]=3,p[3]=0,p[2]=2;s.insert(p);
    p[0]=0,p[1]=2,p[2]=3,p[3]=1;s.insert(p);
    p[0]=0,p[1]=1,p[2]=2,p[3]=3;s.insert(p);
    for(int i=0;i<s.size();i++){
        set<perm>t=s;
        for(auto x:t)for(auto y:t)s.insert(x*y);
    }
//  for(auto x:s)printf("%d %d %d %d\n",x[0],x[1],x[2],x[3]);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%s",g[i]+1);
    for(int i=1;i<=(n>>1);i++)for(int j=1;j<=(m>>1);j++){
        int I=(n+1)-i,J=(m+1)-j;
        set<perm>t;
        perm p;p[0]=g[i][j],p[1]=g[i][J],p[2]=g[I][j],p[3]=g[I][J];
        for(auto x:s)t.insert(x*p); 
        res=1ll*res*t.size()%mod;
        bool ok=true;
        for(int u=0;u<4;u++)for(int v=u+1;v<4;v++)if(p[u]==p[v])ok=false;
        sp[i-1][j-1]=ok;
    }
    if(n&1){
        bool ok=false;
        for(int i=1;i<=m;i++)if(g[(n+1)>>1][i]!=g[(n+1)>>1][m-i+1])ok=true;
        if(ok)(res<<=1)%=mod;
    }
    if(m&1){
        bool ok=false;
        for(int i=1;i<=n;i++)if(g[i][(m+1)>>1]!=g[n-i+1][(m+1)>>1])ok=true;
        if(ok)(res<<=1)%=mod;
    }
    n>>=1,m>>=1;
//  for(int i=0;i<n;i++){for(int j=0;j<m;j++)printf("%d",sp[i][j]);puts("");}
    for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(sp[i][j])bs[i].set(i*m+j),bs[n+j].set(i*m+j);
    for(int i=0,j=0;i<n*m;i++){
        if(!bs[j].test(i))for(int k=j+1;k<n+m;k++)if(bs[k].test(i)){swap(bs[j],bs[k]);break;}
        if(!bs[j].test(i))continue;
        (res<<=1)%=mod;
        for(int k=j+1;k<n+m;k++)if(bs[k].test(i))bs[k]^=bs[j];
        j++;
    }
    printf("%d\n",res);
    return 0;
}