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

using namespace std;
typedef long long LL;
const int a[6][14] = {
    {0, 2, 3, 4, 7, 13},
    {0, 1, 3},
    {0, 20, 15, 87},
    {0, 400, 75, 849, 4995},
    {0, 8000, 375, 8295, 72279, 1024071, 10979127, 137621799},
    {0, 160000, 1875, 81057, 1048923, 28271577, 473368227, 818997991, 826191587, 703745817, 384315988, 54405368, 116074446, 239155320}
};
const int c[6][12] = {
    {0, 1, 2, 3, 6, 12},
    {3},
    {3, 6},
    {5, 18, -24},
    {5, 92, -56, -920, 192, 1152},
    {13, 278, -2372, -11584, 98256, 68096, -1208064, 753664, 4509696, -4485120, -4571136, 4718592}
};
const int b[6][14] = {
    {0, 2, 2, 3, 3, 7},
    {0, 1, 20},
    {0, 3, 15},
    {0, 9, 87, 849},
    {0, 27, 351, 4995},
    {0, 81, 1575, 38457, 1024071, 28271577, 792881031, 431370115}
};
const int d[6][12] = {
    {0, 1, 1, 2, 2, 6},
    {20},
    {5},
    {11, -12},
    {17, -36},
    {45, -518, 1268, 1704, -4064, 1536}
};
const int mod = 998244353;

int ans, t, n, m;

struct Matrix {
    int x[12][12];
    void init(int n, const int a[][12]) {
        int i, j;

        for (i = a[0][n] - 1; i >= 0; i--)
            x[i][a[0][n] - 1] = a[n][a[0][n] - 1 - i];

        for (i = 1; i < a[0][n]; i++)
            x[i][i - 1] = 1;
    }
    friend Matrix operator*(Matrix a, Matrix b) {
        Matrix c;
        int i, j, k;
        memset(c.x, 0, sizeof(c.x));

        for (i = 0; i < 12; i++)
            for (j = 0; j < 12; j++)
                for (k = 0; k < 12; k++)
                    c.x[i][j] = (1ll * a.x[i][k] * b.x[k][j] + c.x[i][j]) % mod;

        return c;
    }
    friend Matrix operator%(Matrix a, int b) {
        return a;
    }
} x, s, e;
template<class T>
T ksmul(T x, LL y, T r) {
    for (; y; y >>= 1, x = (x * x) % mod)
        if (y & 1)
            r = r * x % mod;

    return r;
}
int main() {
    cin >> t;
    int i, j, k;

    while (t--) {
        cin >> n >> m;
        x = e, ans = ksmul(20ll, 1ll * n * m, 1ll);

        if (n <= 5) {
            if (m <= a[0][n])
                ans = (ans + mod - 20ll * a[n][m] % mod) % mod;
            else {
                m -= a[0][n] + 1;
                x.init(n, c);
                s = ksmul(x, m, x);

                for (i = 2; i <= a[0][n]; i++)
                    ans = (ans + mod - 20ll * a[n][i] % mod * s.x[i - 2][a[0][n] - 2] % mod) % mod;
            }
        } else {
            if (n <= b[0][m])
                ans = (ans + mod - 20ll * b[m][n] % mod) % mod;
            else {
                n -= b[0][m] + 1;
                x.init(m, d);
                s = ksmul(x, n, x);

                for (i = 2; i <= b[0][m]; i++)
                    ans = (ans + mod - 20ll * b[m][i] % mod * s.x[i - 2][b[0][m] - 2] % mod) % mod;
            }
        }

        cout << ans << endl;
    }

    return 0;
}

「2017 山东二轮集训 Day4」蜜蜂 题解

算法标签

容斥原理、矩阵快速幂、线性递推、预处理、动态规划（状态压缩）

题目分析

核心问题转化

题目要求计算“特殊网格”的数量，直接枚举或计数特殊网格难度极高，核心思路是 “总网格数 - 非特殊网格数”（容斥原理）：

• 总网格数：每个格子有20种气味选择，n行m列的总网格数为 $20^{n \times m} \mod 998244353$。
• 非特殊网格数：所有8邻域相邻（横向、斜向）的格子，其气味在正二十面体上均相邻的网格数。题目关键约束是 $\min(n,m) \leq 5$，可利用小维度特性预处理+递推求解。

关键前提（正二十面体特性）

正二十面体的每个面（对应一种气味）有 3个相邻面（由样例和代码推导得出）：若两个格子气味对应的面相邻，则有3种合法选择（相对于当前格子的气味）。

核心约束与破局点

• 大维度问题：n或m可达 $10^9$，无法直接递推，需用 矩阵快速幂 加速线性递推。
• 小维度特性：$\min(n,m) \leq 5$，可预处理小维度下的非特殊网格数，再通过线性递推公式扩展到大维度。

核心思路

1. 总网格数计算：用快速幂计算 $20^{n \times m} \mod 998244353$（代码中 ksmul(20ll, 1ll * n * m, 1ll)）。
2. 非特殊网格数计算：
   • 分情况讨论：若 $n \leq 5$（小维度为行），按列数m递推；若 $m \leq 5$（小维度为列），按行数n递推（行列对称）。
   • 预处理：对小维度的每个可能值，提前存储前k个大维度的非特殊网格数（除以20，代码中a、b数组）。
   • 线性递推：当大维度超过预处理范围时，利用线性递推关系（代码中c、d数组）构建转移矩阵，通过矩阵快速幂计算第k项。
3. 答案计算：答案 =（总网格数 - 非特殊网格数）$\mod 998244353$（非特殊网格数 = $20 \times$ 预处理/递推值）。

代码解析

1. 预处理数组说明

代码中4个核心数组为提前推导的“小维度-大维度”非特殊网格数（或递推系数），无需手动计算，直接用于查询和矩阵构建： | 数组 | 用途 | 核心含义 | |------|------|----------| | a[6][14] | 小维度为行（n≤5） | a[n][m] 表示n行m列的非特殊网格数 ÷ 20 | | b[6][14] | 小维度为列（m≤5） | b[m][n] 表示n行m列的非特殊网格数 ÷ 20 | | c[6][12] | 行小维度递推系数 | 对应n≤5时的线性递推特征方程系数 | | d[6][12] | 列小维度递推系数 | 对应m≤5时的线性递推特征方程系数 | | 辅助数组 | - | a[0][n] 表示n行时预处理的最大列数；b[0][m] 表示m列时预处理的最大行数 |

2. 矩阵结构与构建

矩阵作用

将线性递推关系转化为矩阵乘法，支持 $O(\log k)$ 计算第k项（k为大维度，达 $10^9$）。

矩阵构建（Matrix::init 函数）

对于线性递推式 $f(k) = c_1 f(k-1) + c_2 f(k-2) + ... + c_d f(k-d)$：

• 构建d阶转移矩阵，第一行填入递推系数 $[c_1, c_2, ..., c_d]$。
• 其余行按“单位矩阵下移”填充（第i行第i-1列为1），保证递推关系成立。

3. 矩阵快速幂（ksmul 函数）

• 模板化实现矩阵快速幂，支持矩阵乘法和幂次运算，时间复杂度 $O(d^3 \log k)$（d为矩阵维度，最大12，可忽略）。
• 初始矩阵为单位矩阵，通过二进制分解加速幂次计算。

4. 分情况计算逻辑

if (n <= 5) { // 小维度为行，大维度为列m
    if (m <= a[0][n]) {
        // 直接使用预处理值
        非特殊数 = 20 * a[n][m] mod mod;
    } else {
        // 矩阵快速幂递推大维度m
        m -= a[0][n] + 1; // 调整递推起始位置
        构建转移矩阵（基于c数组）;
        矩阵快速幂计算第m项;
        累加预处理值与递推值，得到非特殊数;
    }
} else { // 小维度为列，大维度为行n（交换角色）
    if (n <= b[0][m]) {
        非特殊数 = 20 * b[m][n] mod mod;
    } else {
        n -= b[0][m] + 1;
        构建转移矩阵（基于d数组）;
        矩阵快速幂计算第n项;
        累加预处理值与递推值，得到非特殊数;
    }
}

5. 样例验证（n=1，m=2）

• 总网格数：$20^{1×2} = 400$。
• 非特殊数：$20 \times a[1][2] = 20×3 = 60$（a[1][2] = 3，预处理直接查询）。
• 答案：$(400 - 60) \mod 998244353 = 340$，与样例一致。

复杂度分析

时间复杂度

• 每组测试数据：$O(d^3 \log k)$（k为大维度，$10^9$；d为矩阵维度，最大12）。
• 总复杂度：$O(t \times 12^3 \times 30) = O(t)$（t≤1000），完全适配数据范围。

空间复杂度

• 预处理数组固定大小（最大6×14），矩阵存储为12×12数组，总空间 $O(1)$。

关键注意事项

1. 模运算处理：答案计算时需先加mod再取模，避免负数（代码中 (ans + mod - 非特殊数) % mod）。
2. 行列对称：当n>5但m≤5时，交换n和m的角色，使用b、d数组计算，确保小维度始终被优先处理。
3. 递推起始位置：大维度超过预处理范围时，需调整偏移量（m -= a[0][n] + 1），确保递推公式正确。
4. 非特殊数缩放：预处理数组a、b存储的是“非特殊数 ÷ 20”，计算时需乘以20还原。