「赵州桥」涂色问题题解

问题分析

我们需要计算从第 $1$ 关到第 $n$ 关的所有方案数之和：

• 第 $i$ 关：桥长 $i$，有 $2i$ 个格子
• 要求相邻格子颜色不同
• 最后结果乘以 $(2i)^m$
• 所有关的结果求和后对 $p$ 取模

核心思路

这个问题可以转化为矩阵快速幂和找循环节两种解法，根据数据规模选择合适的方法。

算法详解

1. 问题转化

对于长度为 $i$ 的桥（$2i$ 个格子），涂色方案数可以表示为递推形式。代码中关键递推式为：

val = 1ll * val * ((m - 2) * (m - 1) + 1) % mod;

这实际上是在计算：$f(i) = f(i-1) \times [(m-2)(m-1) + 1]$

2. 两种解法

解法一：矩阵快速幂（当 $m \leq 200$）

namespace O1 {
// 构建转移矩阵
tran[1][1] = (m - 2) * (m - 1) + 1;
for (int j = 2; j <= m + 1; ++j) {
    for (int i = 1; i <= j; ++i) {
        tran[i][j] = tran[i - 1][j - 1] + tran[i][j - 1];
        gmod(tran[i][j]);
    }
}
tran[m + 1][m + 2] = 1;
tran[m + 2][m + 2] = 1;

// 矩阵快速幂
while (n) {
    if (n & 1) {
        mulf();  // f = f * tran
    }
    multran();   // tran = tran * tran
    n >>= 1;
}
}

复杂度：$O(m^3 \log n)$，适合 $m$ 较小的情况。

解法二：找循环节（当 $m > 200$）

namespace O2 {
// 预处理幂次
for (int i = 0; i < mod; ++i) {
    pw[i] = 1;
    for (int j = 1; j <= m; ++j) {
        pw[i] = pw[i] * i % mod;
    }
}

// 找循环节
for (int i = 1; i <= n; ++i) {
    if (vis[i % mod][val] == 2) {  // 找到循环节
        // 计算循环节内的和，乘以循环次数
        ans = (ans + ((n - i + 1) / cnt) % mod * sum) % mod;
        // 处理剩余部分
        for (int j = i + (n - i + 1) / cnt * cnt; j <= n; ++j) {
            ans = (ans + pw[j % mod] * val) % mod;
            val = 1ll * val * ((m - 2) * (m - 1) + 1) % mod;
        }
        break;
    }
    // 记录状态
    ++vis[i % mod][val];
    ans = (ans + pw[i % mod] * val) % mod;
    val = 1ll * val * ((m - 2) * (m - 1) + 1) % mod;
}
}

复杂度：$O(\text{mod}^2)$，适合 $p$ 较小的情况。

3. 最终计算

两种方法最后都进行相同的后处理：

// 乘以 2^m
for (int i = 1; i <= m; ++i) {
    ans <<= 1;
    gmod(ans);
}
// 乘以 m(m-1)
ans = 1ll * ans * m * (m - 1) % mod;

关键技巧

1. 模运算优化

#define gmod(x) (x>=mod?x-=mod:0)

使用宏定义优化模运算，避免昂贵的 % 操作。

2. 状态压缩

在找循环节时，使用 vis[i % mod][val] 来记录状态，其中：

• i % mod：当前关数对模数取模
• val：当前的递推值

3. 循环节检测

当同一个 (i % mod, val) 状态出现两次时，说明找到了循环节，可以大幅减少计算量。

复杂度分析

• 矩阵快速幂：$O(m^3 \log n)$，适合 $m \leq 200$
• 循环节查找：期望 $O(\text{mod}^2)$，适合 $p \leq 3000$

样例验证

样例：n=2, m=5, p=50

• 第1关：$2^5 \times \text{方案数} = 32 \times 20 = 640$
• 第2关：$4^5 \times \text{方案数} = 1024 \times 260 = 266240$
• 总和：$640 + 266240 = 266880$
• 模50：$266880 \bmod 50 = 30$

总结

本题的巧妙之处在于：

1. 问题分解：将复杂涂色问题转化为线性递推
2. 算法选择：根据数据规模选择矩阵快速幂或循环节查找
3. 优化技巧：模运算优化、状态压缩、循环节检测
4. 数学建模：正确推导涂色方案的递推关系

这种"多算法选择 + 数学建模"的方法在解决复杂计数问题时非常有效。