题解：奇怪的数

源题目地址：https://www.lanqiao.cn/problems/3528/learning/

问题分析

我们需要找到满足以下条件的长度为 ( n ) 的数字：

1. 奇数位是奇数，偶数位是偶数：即在奇数位置上只能是 ( 1, 3, 5, 7, 9 )，在偶数位置上只能是 ( 0, 2, 4, 6, 8 )。
2. 任意连续 5 个数位的和不超过 ( m \times m )：这是一个滑动窗口限制。

最终目标是统计所有满足上述条件的数字个数，并对结果取模 ( 998244353 )。

解题思路

为了高效解决该问题，我们采用动态规划DP的方法。以下是详细的解题步骤：

---

动态规划设计

定义状态 ( dp[a][b][c][d] ) 表示当前数字的最后 4 个数位分别为 ( a, b, c, d ) 时，满足条件的数字个数。

• 状态转移：

  • 当前数字的第 ( i ) 位可以由前一个状态的最后 4 位推导而来。
  • 新的一位 ( x ) 必须满足：
    1. 奇偶性约束：如果 ( i ) 是奇数位，则 ( x ) 必须是奇数；如果是偶数位，则 ( x ) 必须是偶数。
    2. 和约束：新加入的 5 位数字之和不能超过 ( m \times m )。

• 边界初始化：

  • 对于前 4 位数字，直接枚举所有可能的组合，满足奇偶性和和约束，将其初始化为 1。

• 优化：

  • 利用滚动数组减少内存开销。
  • 在状态转移过程中，及时清空无用的状态以节省空间。

---

代码实现

import java.util.Scanner;

public class Main {
 static final int mod = 998244353;
 static int[][][][] dp = new int[10][10][10][10];

 public static void main(String[] args) {
 	Scanner scanner = new Scanner(System.in);
 	int n = scanner.nextInt();
 	int m = scanner.nextInt();
 	int res = 0;

 	// 初始化边界
 	for (int i = 1; i <= 9; i += 2) {
 		for (int j = 0; j <= 9 && j <= (m - i); j += 2) {
 			for (int k = 1; k <= 9 && k <= (m - i - j); k += 2) {
 				for (int l = 0; l <= 9 && l <= (m - i - j - k); l += 2) {
 					dp[i][j][k][l] = 1;// 边界初始化为1
 				}
 			}
 		}
 	}

 	// 开始动态规划
 	for (int i = 5; i <= n; i++) {// 遍历数字的位数
 		for (int p = i % 2; p <= 9; p += 2) {// 遍历当前数字的奇数位数
 			for (int j = (i + 1) % 2; j <= 9 && (j <= m - p); j += 2) {// 遍历当前数字的偶数位数
 				for (int k = i % 2; k <= 9 && (k <= m - p - j); k += 2) {// 遍历奇数
 					for (int l = (i + 1) % 2; l <= 9 && l <= (m - p - j - k); l += 2) {// 遍历偶数
 						for (int q = i % 2; q <= 9 && q <= (m - p - j - k - l); q += 2) {// 遍历最后一个奇数位
 							dp[j][k][l][q] += dp[p][j][k][l];// 状态转移
 							dp[j][k][l][q] %= mod;
 						}
 						dp[p][j][k][l] = 0;// 清空原有的值
 					}
 				}
 			}
 		}
 	}

 	// 计算结果
 	for (int j = (n + 1) % 2; j <= 9 && (j <= m); j += 2) {
 		for (int k = n % 2; k <= 9 && (k <= m - j); k += 2) {
 			for (int l = (n + 1) % 2; l <= 9 && l <= (m - j - k); l += 2) {
 				for (int q = n % 2; q <= 9 && q <= (m - j - k - l); q += 2) {
 					res += dp[j][k][l][q];// 累加结果
 					res %= mod;
 				}
 			}
 		}
 	}
 	System.out.println(res);
 }
}

算法实现

代码实现中，主要分为以下几个部分：

1. 初始化边界：

   for (int i = 1; i <= 9; i += 2) {
       for (int j = 0; j <= 9 && j <= (m - i); j += 2) {
           for (int k = 1; k <= 9 && k <= (m - i - j); k += 2) {
               for (int l = 0; l <= 9 && l <= (m - i - j - k); l += 2) {
                   dp[i][j][k][l] = 1;
               }
           }
       }
   }
   

   这里枚举了前 4 位的所有可能组合，并初始化符合条件的状态。

2. 动态规划状态转移：

   for (int i = 5; i <= n; i++) {
       for (int p = i % 2; p <= 9; p += 2) {
           for (int j = (i + 1) % 2; j <= 9 && (j <= m - p); j += 2) {
               for (int k = i % 2; k <= 9 && (k <= m - p - j); k += 2) {
                   for (int l = (i + 1) % 2; l <= 9 && l <= (m - p - j - k); l += 2) {
                       for (int q = i % 2; q <= 9 && q <= (m - p - j - k - l); q += 2) {
                           dp[j][k][l][q] += dp[p][j][k][l];
                           dp[j][k][l][q] %= mod;
                       }
                       dp[p][j][k][l] = 0;
                   }
               }
           }
       }
   }
   

   从第 5 位开始逐步计算新的状态，并更新 DP 数组。

3. 结果统计：

   for (int j = (n + 1) % 2; j <= 9 && (j <= m); j += 2) {
       for (int k = n % 2; k <= 9 && (k <= m - j); k += 2) {
           for (int l = (n + 1) % 2; l <= 9 && l <= (m - j - k); l += 2) {
               for (int q = n % 2; q <= 9 && q <= (m - j - k - l); q += 2) {
                   res += dp[j][k][l][q];
                   res %= mod;
               }
           }
       }
   }
   

   最后累加所有可能的状态，得到最终结果。

---

复杂度分析

1. 时间复杂度：

   • 初始化边界的时间复杂度为 ( O(10^4) )。
   • 动态规划状态转移的时间复杂度为 ( O(n \cdot 10^4) )，其中 ( n ) 是数字长度。
   • 总体时间复杂度为 ( O(n \cdot 10^4) )，在 ( n \leq 2 \times 10^5 ) 的范围内可接受。

2. 空间复杂度：

   • 使用了一个大小为 ( 10 \times 10 \times 10 \times 10 ) 的 DP 数组，空间复杂度为 ( O(10^4) )。

---

示例验证

输入：

5 5

输出：

6

解释：
当 ( n = 5 ) 且 ( m = 5 ) 时，满足条件的数字有 6 个。

---

总结

通过动态规划巧妙地解决了复杂的约束问题，充分利用了奇偶性和滑动窗口的性质。代码逻辑清晰、实现正确，能够高效处理大规模数据。