C++递推实战：信息学奥赛1313题“位数问题”的3种边界条件处理与取模技巧

在信息学竞赛的递推类题目中，"位数问题"是一个经典且高频出现的题型。这类问题往往考察选手对数字性质的理解以及递推关系的建立能力。今天，我们就以1313题为例，深入剖析递推算法在实际编码中的关键细节，特别是三种边界条件的处理方法和取模运算的技巧。

1. 问题分析与递推关系建立

首先，让我们明确题目要求：计算所有N位数中，包含偶数个数字3的数的个数，结果对12345取模。这里的N位数指的是从100...0（N-1个0）到999...9（N个9）之间的所有整数。

递推关系的核心思路是将问题分解为更小的子问题。我们可以定义两个数组：

• a[i]：i位数中有偶数个3的数字数量
• b[i]：i位数中有奇数个3的数字数量

对于1位数的情况（基础情况）：

• 有偶数个3的数字：0,1,2,4,5,6,7,8,9 → 共9个
• 有奇数个3的数字：只有3 → 共1个

因此初始条件为：

a[1] = 9; // 1位数中有9个数字包含偶数个3 b[1] = 1; // 1位数中有1个数字包含奇数个3

对于i位数（i>1），递推关系需要考虑两种情况：

1. 前i-1位已经有偶数个3，第i位不是3
2. 前i-1位有奇数个3，第i位是3

因此递推公式为：

a[i] = (a[i-1] * 9 + b[i-1]) % MOD; b[i] = (a[i-1] + b[i-1] * 9) % MOD;

注意：这里的MOD值为12345，需要在每次运算后取模，防止数值溢出。

2. 三种边界条件的处理技巧

在实际编码中，边界条件的处理往往决定了程序的正确性。对于这个问题，我们需要特别注意三种边界情况：

2.1 i=1时的初始化处理

1位数的情况比较特殊，因为：

• 数字0在1位数中是合法的（虽然N位数时首位不能为0）
• 只有数字3包含奇数个3

常见的错误初始化方式：

// 错误示例：忽略了数字0的情况 a[1] = 8; // 错误！实际上应该是9 b[1] = 1;

正确的初始化应该明确考虑所有1位数：

// 正确初始化 a[1] = 9; // 0,1,2,4,5,6,7,8,9 b[1] = 1; // 3

2.2 i=n时的最高位处理

当处理到第n位（最高位）时，数字不能以0开头，因此非3的选择从9种减少到8种（1,2,4,5,6,7,8,9）。这需要在循环中特殊处理：

int K = 9; // 一般情况下有9种选择（0-9，除了3） for(int i=2; i<=n; i++) { if(i == n) K = 8; // 最高位不能为0 a[i] = (a[i-1]*K + b[i-1]) % MOD; b[i] = (a[i-1] + b[i-1]*K) % MOD; }

2.3 数组大小的设定

由于题目没有明确给出N的最大值，我们需要合理设定数组大小。考虑到：

• 现代计算机的内存充足
• 题目通常不会设置过大的N（一般N≤1000）
• 结果需要对12345取模，数值不会太大

建议的数组大小设定：

#define MAXN 1005 // 适当留有余量 int a[MAXN], b[MAXN];

3. 取模运算的注意事项

在递推过程中，数值可能非常大，因此需要及时取模。但取模运算有几个关键点需要注意：

3.1 运算顺序的影响

错误的运算顺序可能导致中间结果溢出：

// 错误示例：可能导致溢出 a[i] = a[i-1]*9 % MOD + b[i-1] % MOD;

正确的做法是将整个表达式括起来再取模：

// 正确做法 a[i] = (a[i-1]*9 + b[i-1]) % MOD;

3.2 负数的处理

在某些情况下，减法运算可能产生负数，这时需要调整：

// 处理可能出现的负数 int result = (a - b) % MOD; if(result < 0) result += MOD;

3.3 大数相乘的溢出

当N很大时，即使每次取模，中间结果仍可能溢出。可以使用long long类型：

a[i] = (1LL * a[i-1] * K + b[i-1]) % MOD;

4. 完整代码实现与常见错误分析

结合以上分析，我们给出完整的代码实现：

#include <iostream> using namespace std; const int MOD = 12345; const int MAXN = 1005; int main() { int n; cin >> n; int a[MAXN], b[MAXN]; a[1] = 9; b[1] = 1; int K = 9; for(int i=2; i<=n; i++) { if(i == n) K = 8; // 最高位不能为0 a[i] = (1LL * a[i-1] * K + b[i-1]) % MOD; b[i] = (1LL * b[i-1] * K + a[i-1]) % MOD; } cout << a[n] << endl; return 0; }

常见错误分析：

1. 忽略最高位不能为0：

   • 错误：所有位数都使用相同的乘数9
   • 现象：当n≥2时，结果偏大

2. 初始化错误：

   • 错误：a[1]=8（忽略了数字0）
   • 现象：所有结果都会偏小

3. 取模不完全：

   • 错误：只在最后输出时取模
   • 现象：当n较大时，结果溢出变为负数

4. 数组越界：

   • 错误：数组大小不足
   • 现象：当n较大时，程序崩溃或输出错误

5. 性能优化与扩展思考

虽然这个问题的标准解法时间复杂度已经是O(n)，非常高效，但我们还可以考虑一些优化和扩展：

5.1 空间优化

注意到递推公式只依赖于前一个状态，因此可以优化空间复杂度到O(1)：

int a_prev = 9, b_prev = 1; int K = 9; for(int i=2; i<=n; i++) { if(i == n) K = 8; int a_curr = (1LL * a_prev * K + b_prev) % MOD; int b_curr = (1LL * b_prev * K + a_prev) % MOD; a_prev = a_curr; b_prev = b_curr; } cout << a_prev << endl;

5.2 数学公式推导

通过数学推导，我们可以得到一个非递推的公式解：

a[n] = (8 * 9^(n-1) + 1) / 2 % MOD b[n] = (8 * 9^(n-1) - 1) / 2 % MOD

不过由于涉及除法取模，需要计算模逆元，实现起来反而更复杂。

5.3 问题变种思考

这个问题可以有多种变种，例如：

• 计算包含特定数量（不一定是偶数）的数字3的数
• 考虑其他数字的限制（如不允许连续两个3）
• 扩展到其他进制（如二进制、十六进制）

每种变种都需要重新分析递推关系，但基本思路是相通的。