一、问题分析

1.1 问题描述

给定一个立方体框架（12条边），需要在每条边上放置一个单词，使得：

1. 每条边上的单词来自给定的单词列表
2. 每条边可以双向阅读（正读或反读有意义即可）
3. 求有多少种不同的填词方案（模 $998244353$）

1.2 核心观察

观察1：立方体的结构

立方体有：

• 8个顶点
• 12条边（每条边连接2个顶点）
• 每个顶点与3条边相连

观察2：顶点与字母的对应关系

关键洞察：如果我们给每个顶点分配一个字母，那么每条边对应的单词的首尾字母就是该边两个端点的字母。

因此，问题转化为：

1. 给8个顶点分配字母
2. 检查12条边对应的"字母对"是否存在匹配的单词

观察3：立方体的对称性

立方体的8个顶点可以用三维坐标 $(x,y,z)$ 表示，其中 $x,y,z \in \{0,1\}$。

两个顶点相邻（有边相连）当且仅当它们恰好有一个坐标不同。

例如：$(0,0,0)$ 与 $(1,0,0)$、$(0,1,0)$、$(0,0,1)$ 相邻。

观察4：独立集分解

立方体的8个顶点可以分成两组，每组4个顶点，组内任意两点不相邻：

• 第一组（坐标和为偶数）：$\{(0,0,0), (0,1,1), (1,0,1), (1,1,0)\}$
• 第二组（坐标和为奇数）：$\{(1,1,1), (1,0,0), (0,1,0), (0,0,1)\}$

这两组形成立方体的二分图结构，所有12条边都连接两组之间的顶点。

二、数学建模

2.1 问题转化

设第一组4个顶点的字母为 $a, b, c, d$，第二组4个顶点的字母为 $A, B, C, D$。

根据立方体的结构，每条边连接一组中的一个顶点和另一组中的三个顶点。

关键发现：第一组的每个顶点恰好与第二组的3个顶点相邻。

例如，顶点 $(0,0,0)$ 与 $(1,0,0)$、$(0,1,0)$、$(0,0,1)$ 相邻。

2.2 计数模型

设：

• $\text{cnt}[\ell][x][y]$ 表示长度为 $\ell$、首字母为 $x$、尾字母为 $y$ 的单词数量
• $f[x][y][z]$ 表示某个顶点与字母为 $x, y, z$ 的三个顶点相邻的方案数

则：

$$f[x][y][z] = \sum_{j=0}^{61} \text{cnt}[\ell][j][x] \cdot \text{cnt}[\ell][j][y] \cdot \text{cnt}[\ell][j][z] $$

这表示：存在一个字母为 $j$ 的顶点，它与字母为 $x, y, z$ 的三个顶点通过边相连。

2.3 总方案数计算

枚举第一组的4个顶点的字母 $a, b, c, d$，则第二组的4个顶点必须满足：

• 顶点A与 $b, c, d$ 相邻（不与 $a$ 相邻）
• 顶点B与 $a, c, d$ 相邻（不与 $b$ 相邻）
• 顶点C与 $a, b, d$ 相邻（不与 $c$ 相邻）
• 顶点D与 $a, b, c$ 相邻（不与 $d$ 相邻）

因此总方案数为：

$$\text{ans} = \sum_{a,b,c,d} f[b][c][d] \cdot f[a][c][d] \cdot f[a][b][d] \cdot f[a][b][c] $$

其中：

• $f[b][c][d]$：顶点A（与 $b,c,d$ 相邻）的贡献
• $f[a][c][d]$：顶点B（与 $a,c,d$ 相邻）的贡献
• $f[a][b][d]$：顶点C（与 $a,b,d$ 相邻）的贡献
• $f[a][b][c]$：顶点D（与 $a,b,c$ 相邻）的贡献

2.4 正确性证明

定理1：上述计数方法不重不漏。

证明：

唯一性：每种填词方案对应唯一的8个顶点字母分配 $(a,b,c,d,A,B,C,D)$，其中 $(a,b,c,d)$ 是第一组顶点的字母。

完整性：对于任意合法的字母分配，我们的枚举都会统计到。

计数正确性：

• $f[x][y][z]$ 统计了所有可能的"中心顶点"字母
• 四个 $f$ 值的乘积恰好对应12条边的所有单词选择方案
• 使用乘法原理，每条边的选择独立

三、代码模块详解

模块1：全局定义与常量

#define int long long
const int N = 1e5 + 5;
const int S = 66;
const int Mod = 998244353;

说明：

• int 定义为 long long 防止中间计算溢出
• N：单词数量上限
• S：字符集大小（62个字符：a-z, A-Z, 0-9）
• Mod：模数 $998244353$

模块2：辅助函数

void add(int &x, int y) {
    x += y;
    x -= (x >= Mod) * Mod;
}

int ask(char x) {
    if (x >= 'a' && x <= 'z') {
        return x - 'a';
    }
    if (x >= 'A' && x <= 'Z') {
        return x - 'A' + 26;
    }
    return x - '0' + 52;
}

add 函数：

• 功能：模意义下加法
• 实现：x += y; if (x >= Mod) x -= Mod;
• 避免频繁取模操作，提高效率

ask 函数：

• 功能：将字符映射到 $[0, 61]$ 的整数
• 映射规则：
  • a-z → $[0, 25]$
  • A-Z → $[26, 51]$
  • 0-9 → $[52, 61]$

模块3：数据结构定义

string s[N * 2];
int cnt[11][S][S];
int f[S][S][S];
int n;

变量说明：

• s[N * 2]：存储单词及其反转（双向阅读）
• cnt[len][first][last]：长度为 $\text{len}$、首字母为 $\text{first}$、尾字母为 $\text{last}$ 的单词数量
• f[x][y][z]：某个顶点与字母为 $x, y, z$ 的三个顶点相邻的方案数

模块4：输入与预处理

cin >> n;

for (int i = 1; i <= n; i++) {
    cin >> s[i];
    s[i + n] = s[i];
    reverse(s[i].begin(), s[i].end());
}

sort(s + 1, s + 1 + 2 * n);
int z = unique(s + 1, s + 1 + 2 * n) - s - 1;

for (int i = 1; i <= z; i++) {
    int len = s[i].length();
    cnt[len][ask(s[i][0])][ask(s[i][len - 1])]++;
}

算法流程：

步骤1：读入单词并生成反转

由于每条边可以双向阅读，我们需要：

• 原单词：s[i]
• 反转单词：s[i + n] = reverse(s[i])

例如："FLOW" → 同时考虑 "FLOW" 和 "WOLF"

步骤2：排序去重

使用 sort 和 unique 去除重复单词（如回文串）。

例如："radar" 的反转仍是 "radar"，只需保留一个。

步骤3：统计单词的首尾字母

对于每个去重后的单词：

• 提取长度 $\ell$
• 提取首字母 $x = \text{ask}(s[i][0])$
• 提取尾字母 $y = \text{ask}(s[i][\ell-1])$
• 增加计数：cnt[ℓ][x][y]++

时间复杂度：$O(n \log n)$（排序）

模块5：计算 $f$ 数组

for (int i = 3; i <= 10; i++) {
    memset(f, 0, sizeof(f));
    
    for (int j = 0; j < 62; j++) {
        for (int x = 0; x < 62; x++) {
            for (int y = 0; y < 62; y++) {
                for (int z = 0; z < 62; z++) {
                    add(f[x][y][z], cnt[i][j][x]*cnt[i][j][y] % Mod * cnt[i][j][z] % Mod);
                }
            }
        }
    }
    
    // ... 计算答案 ...
}

算法逻辑：

枚举单词长度 $i \in [3, 10]$（题目约束）。

对于每个长度，计算 $f[x][y][z]$：

$$f[x][y][z] = \sum_{j=0}^{61} \text{cnt}[i][j][x] \cdot \text{cnt}[i][j][y] \cdot \text{cnt}[i][j][z] $$

数学意义：

• 枚举中心顶点的字母 $j$
• 枚举与它相邻的三个顶点的字母 $x, y, z$
• 对于每个 $j$，统计从 $j$ 到 $x, y, z$ 的边上可以放置的单词数量的乘积
• 将所有可能的 $j$ 的贡献累加

为什么要分长度计算？

因为立方体的12条边长度必须相同（同一个单词长度），所以需要对每个长度分别计算方案数。

时间复杂度：$O(8 \times 62^4) = O(62^4) \approx 1.5 \times 10^7$（对每个长度）

模块6：计算总方案数

for (int a = 0; a < 62; a++) {
    for (int b = 0; b < 62; b++) {
        for (int c = 0; c < 62; c++) {
            for (int d = 0; d < 62; d++) {
                add(ans, f[a][b][c]*f[b][c][d] % Mod * f[a][b][d] % Mod * f[a][c][d] % Mod);
            }
        }
    }
}

算法逻辑：

枚举第一组4个顶点的字母 $a, b, c, d$。

计算方案数：

$$\text{ans} \mathrel{+}= f[b][c][d] \cdot f[a][c][d] \cdot f[a][b][d] \cdot f[a][b][c] $$

数学推导：

设第二组4个顶点为 $A, B, C, D$，其对应的字母分别与第一组中的3个顶点相邻：

第二组顶点	相邻的第一组顶点	对应的 $f$ 值
A	$b, c, d$（不与 $a$ 相邻）	$f[b][c][d]$
B	$a, c, d$（不与 $b$ 相邻）	$f[a][c][d]$
C	$a, b, d$（不与 $c$ 相邻）	$f[a][b][d]$
D	$a, b, c$（不与 $d$ 相邻）	$f[a][b][c]$

根据乘法原理，总方案数为四个 $f$ 值的乘积。

为什么是这四个 $f$ 值？

这对应立方体的二分图结构。第一组的每个顶点不与某个特定的第二组顶点相邻，形成完美的对应关系。

时间复杂度：$O(62^4) \approx 1.5 \times 10^7$（对每个长度）

模块7：主函数

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    
    // 预处理
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        s[i + n] = s[i];
        reverse(s[i].begin(), s[i].end());
    }
    
    sort(s + 1, s + 1 + 2 * n);
    int z = unique(s + 1, s + 1 + 2 * n) - s - 1;
    
    for (int i = 1; i <= z; i++) {
        int len = s[i].length();
        cnt[len][ask(s[i][0])][ask(s[i][len - 1])]++;
    }
    
    int ans = 0;
    
    // 枚举长度
    for (int i = 3; i <= 10; i++) {
        memset(f, 0, sizeof(f));
        
        // 计算 f 数组
        for (int j = 0; j < 62; j++) {
            for (int x = 0; x < 62; x++) {
                for (int y = 0; y < 62; y++) {
                    for (int z = 0; z < 62; z++) {
                        add(f[x][y][z], cnt[i][j][x]*cnt[i][j][y] % Mod * cnt[i][j][z] % Mod);
                    }
                }
            }
        }
        
        // 计算答案
        for (int a = 0; a < 62; a++) {
            for (int b = 0; b < 62; b++) {
                for (int c = 0; c < 62; c++) {
                    for (int d = 0; d < 62; d++) {
                        add(ans, f[a][b][c]*f[b][c][d] % Mod * f[a][b][d] % Mod * f[a][c][d] % Mod);
                    }
                }
            }
        }
    }
    
    cout << ans << "\n";
    return 0;
}

算法流程总结：

1. 输入单词，生成反转并去重
2. 统计 cnt[len][first][last]
3. 对每个长度 $\ell \in [3, 10]$：
   • 计算 $f[x][y][z]$
   • 枚举 $(a,b,c,d)$ 计算方案数
4. 输出总方案数

四、复杂度分析

4.1 时间复杂度

预处理：

• 读入并反转：$O(n \cdot L)$，其中 $L$ 是单词平均长度
• 排序：$O(n \log n \cdot L)$
• 去重：$O(n)$
• 统计 cnt：$O(n \cdot L)$

主循环：

• 外层枚举长度：8次（长度 3-10）
• 计算 $f$：$O(62^5) \approx 9 \times 10^8$
• 计算答案：$O(62^4) \approx 1.5 \times 10^7$

总时间复杂度：$O(n \log n \cdot L + 8 \times 62^5) \approx O(62^5)$

虽然看起来复杂度很高，但由于常数较小且现代CPU运算速度快，实际可以在时限内通过。

4.2 空间复杂度

数组空间：

• s[]：$O(n \cdot L)$
• cnt[][]：$O(10 \times 62^2) = O(38440)$
• f[][][]：$O(62^3) = O(238328)$

总空间复杂度：$O(n \cdot L + 62^3) \approx O(10^6)$

4.3 优化技巧

1. 模运算优化：使用 add 函数代替 % 运算符
2. 批量取模：连续乘法后再取模，减少取模次数
3. IO优化：ios::sync_with_stdio(0)
4. 空间复用：每个长度单独计算 $f$ 数组，避免存储所有长度的 $f$ 值

六、总结

6.1 核心思想

本题采用的图论建模 + 组合计数的核心思想：

1. 问题转化：填词问题 → 顶点着色问题
2. 结构分析：利用立方体的二分图性质
3. 状态设计：$f[x][y][z]$ 表示三邻接顶点的方案数
4. 乘法原理：独立选择每条边的单词，方案数相乘