题解：

问题理解

我们有一个 $N \times N$ 的网格，每个格子是红色(R)或白色(W)。可以进行以下操作：选择一个 $2 \times 2$ 的子方格，翻转其中所有格子的颜色（R↔W）。

两个网格如果可以通过一系列这样的操作互相转换，则称为相似。给定 $G$ 个网格，求相似网格对的数量。

关键观察

1. 数学建模

将网格看作 $\mathbb{F}_2$（二元域）上的 $N \times N$ 矩阵：

• W(白色) = 0
• R(红色) = 1

$2 \times 2$ 翻转操作相当于在矩阵的 $2 \times 2$ 子块上加上全1矩阵。

2. 变换的不变量

经过分析，我们可以发现一个重要性质：对于一个 $N \times N$ 的网格，定义一个 $(N-1) \times (N-1)$ 的差分矩阵 $D$：

对于 $1 \leq i < N, 1 \leq j < N$：

$$D_{i,j} = A_{i,j} + A_{i+1,j} + A_{i,j+1} + A_{i+1,j+1} \pmod{2} $$

其中 $A$ 是原始网格矩阵。

关键定理：两个网格相似当且仅当它们有相同的差分矩阵 $D$。

证明思路：

• 每个 $2 \times 2$ 翻转操作会改变 $D$ 中的一个元素
• 实际上，$D$ 矩阵完全决定了网格在变换下的等价类
• 网格的第一行和第一列可以任意设定，然后根据 $D$ 唯一确定其他格子

3. 算法步骤

1. 对于每个网格，计算其差分矩阵 $D$
2. 将 $D$ 矩阵编码为一个字符串或哈希值
3. 统计每个编码出现的次数
4. 计算相似网格对数量：对于出现 $k$ 次的编码，贡献 $C(k,2) = k(k-1)/2$ 对

时间复杂度

• 每个网格：$O(N^2)$ 计算差分矩阵
• 总时间：$O(G \cdot N^2)$
• 对于 $N \leq 10, G \leq 10000$，完全可行

C语言实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 10
#define MAX_G 10000
#define MAX_HASH 1000007  // 更大的质数作为哈希表大小

typedef struct {
    long long key;
    int count;
    int next;  // 链表下一个位置
} HashEntry;

HashEntry hashTable[MAX_HASH];
int head[MAX_HASH];
int hashSize = 0;

// 初始化哈希表
void initHash() {
    memset(head, -1, sizeof(head));
    hashSize = 0;
}

// 插入或查找
int findOrInsert(long long key) {
    int h = key % MAX_HASH;
    if (h < 0) h = -h;
    
    // 在链表中查找
    for (int i = head[h]; i != -1; i = hashTable[i].next) {
        if (hashTable[i].key == key) {
            hashTable[i].count++;
            return i;
        }
    }
    
    // 未找到，插入新项
    hashTable[hashSize].key = key;
    hashTable[hashSize].count = 1;
    hashTable[hashSize].next = head[h];
    head[h] = hashSize;
    return hashSize++;
}

int main() {
    int N, G;
    scanf("%d", &N);
    scanf("%d", &G);
    
    initHash();
    
    char grid[MAX_N][MAX_N + 1];
    long long similar_pairs = 0;
    
    for (int g = 0; g < G; g++) {
        // 读取当前网格
        for (int i = 0; i < N; i++) {
            scanf("%s", grid[i]);
        }
        
        // 计算差分矩阵并编码为长整型
        long long code = 0;
        long long bit = 1;
        
        for (int i = 0; i < N - 1; i++) {
            for (int j = 0; j < N - 1; j++) {
                // 计算 D[i][j]
                int sum = 0;
                sum += (grid[i][j] == 'R');
                sum += (grid[i+1][j] == 'R');
                sum += (grid[i][j+1] == 'R');
                sum += (grid[i+1][j+1] == 'R');
                
                if (sum % 2) {
                    code |= bit;
                }
                bit <<= 1;
            }
        }
        
        // 添加到哈希表
        findOrInsert(code);
    }
    
    // 计算相似网格对的数量
    for (int i = 0; i < hashSize; i++) {
        long long k = hashTable[i].count;
        similar_pairs += k * (k - 1) / 2;
    }
    
    printf("%lld\n", similar_pairs);
    
    return 0;
}

样例解释

对于样例输入：

2
2
RW
WR
WR
RW

• 第一个网格：

  RW
  WR
  

  差分矩阵（$1\times1$）：$D = (1+0+0+1) \bmod 2 = 0$

• 第二个网格：

  WR
  RW
  

  差分矩阵：$D = (0+1+1+0) \bmod 2 = 0$

两者差分矩阵相同，因此相似。

总结

本题的关键是将网格相似性问题转化为差分矩阵的等价性问题。通过计算每个网格的差分矩阵并统计相同矩阵的数量，我们可以高效地计算出相似网格对的数量。算法时间复杂度为 $O(G \cdot N^2)$，空间复杂度为 $O(G)$，完全满足题目要求。