代码出现Time Limit Exceed问题：求解数位和为奇数的数字累加和

给定数字n（1 ≤ n < 10^{17），计算1到n中所有数位和为奇数的数字之和，结果取模10}9+7。例如输入13时，结果为1+3+5+7+9+10+12=47。
当前代码通过循环遍历每个数字判断数位和奇偶性并累加，但面对极大n时出现超时问题，请求分析代码问题并提供解决方案。
代码如下：

MOD = 1000000007
def getSum(number):
    total = 0
    while number > 0:
        total += number % 10
        number //= 10
    return (total % MOD) % 2

def sticker(number):
    stickerNeed = 0
    for oneDigit in range(1, number):
        if (getSum(oneDigit % MOD) == 1):
            stickerNeed += oneDigit
    return stickerNeed % MOD


number = int(input())
result = sticker(number)
print(result % MOD)

问题分析 #

• 时间复杂度爆炸：代码采用暴力遍历1到n-1所有数字的方式，时间复杂度为O(n)。当n接近10^{17时，循环次数达到10}17量级，根本不可能在合理时间内完成计算，必然触发超时。
• 冗余计算叠加：getSum函数每次都要逐位计算数字的数位和，对于大数来说这会额外增加时间开销，进一步拖慢程序运行速度。

解决方案 #

要处理这种超大范围的数位统计问题，**数位动态规划（数位DP）**是最优选择。它通过逐位处理数字的每一位，维护状态来统计符合条件的数字数量与总和，时间复杂度仅为O(数字位数)，完全适配n<10^17的场景。

实现代码 #

MOD = 10**9 + 7

def calculate_odd_sum(n):
    s = str(n)
    digit_count = len(s)
    
    # dp[pos][sum_parity][tight] = (count, total_sum)
    # pos: 当前处理到第几位（从0开始）
    # sum_parity: 前pos位的数位和奇偶性，0为偶，1为奇
    # tight: 当前数位是否受原数字n的限制（1受限制，0不受）
    # count: 该状态下符合条件的数字数量，total_sum: 这些数字的总和
    dp = [[[ (0, 0) for _ in range(2)] for __ in range(2)] for ___ in range(digit_count + 1)]
    dp[0][0][1] = (1, 0)  # 初始状态：0位数字，和为偶，受限制，数量1（代表空数字），总和0
    
    for pos in range(digit_count):
        current_max_digit = int(s[pos])
        for sum_parity in range(2):
            for tight in range(2):
                current_cnt, current_total = dp[pos][sum_parity][tight]
                if current_cnt == 0:
                    continue
                
                # 确定当前位可选取的最大数字
                upper_limit = current_max_digit if tight else 9
                for d in range(0, upper_limit + 1):
                    new_tight = 1 if (tight and d == upper_limit) else 0
                    new_sum_parity = (sum_parity + d) % 2
                    
                    # 计算当前位d对总和的贡献：d * 10^(剩余位数) * 当前状态的数字数量 + 已有总和
                    power = 10 ** (digit_count - pos - 1) % MOD
                    digit_contribution = (d * power) % MOD
                    new_total = (current_total + digit_contribution * current_cnt) % MOD
                    
                    # 更新dp状态
                    old_cnt, old_total = dp[pos+1][new_sum_parity][new_tight]
                    dp[pos+1][new_sum_parity][new_tight] = (
                        (old_cnt + current_cnt) % MOD,
                        (old_total + new_total) % MOD
                    )
    
    # 所有数位处理完成后，统计数位和为奇数的数字总和（包含0，但0的数位和为偶，不影响结果）
    total_odd = (dp[digit_count][1][0][1] + dp[digit_count][1][1][1]) % MOD
    return total_odd

n = int(input())
print(calculate_odd_sum(n) % MOD)

代码说明 #

• 数位DP的核心是状态维护：dp[pos][sum_parity][tight]记录了处理到第pos位时，前pos位和的奇偶性为sum_parity、是否受原数字限制的情况下，符合条件的数字数量与总和。
• 递推过程中，我们遍历每个数位的可能取值，更新状态并计算对应的总和贡献，彻底避免了暴力遍历所有数字的低效操作。
• 对于17位的数字，计算量仅为10172*2=680次，完全不会出现超时问题。

内容的提问来源于stack exchange，提问作者zeliha