Hard

题目描述

给你三个整数 l、r 和 k。

考虑所有由恰好 k 位数字组成的整数，其中每一位数字都从整数范围 [l, r]（包含边界）中独立选择。如果范围中包含 0，则允许前导零。

返回一个整数，表示所有这些数字的和。由于答案可能非常大，请返回对 10^9 + 7 取模的结果。

示例 1：

输入：l = 1, r = 2, k = 2
输出：66
解释：
使用范围 [1, 2] 中的 k = 2 位数字形成的所有数字为 11, 12, 21, 22。
总和为 11 + 12 + 21 + 22 = 66。

示例 2：

输入：l = 0, r = 1, k = 3
输出：444
解释：
使用范围 [0, 1] 中的 k = 3 位数字形成的所有数字为 000, 001, 010, 011, 100, 101, 110, 111。
去掉前导零后，这些数字为 0, 1, 10, 11, 100, 101, 110, 111。
总和为 444。

示例 3：

输入：l = 5, r = 5, k = 10
输出：555555520
解释：
5555555555 是唯一一个由范围 [5, 5] 中的 k = 10 位数字组成的有效数字。
总和为 5555555555 % (10^9 + 7) = 555555520。

约束条件：

  • 0 <= l <= r <= 9
  • 1 <= k <= 10^9

解题思路

这是一道组合数学问题，需要利用数学公式来快速计算。

核心思路：

  1. 总数统计：对于k位数，每一位都可以从[l,r]范围选择，总共有(r-l+1)^k个数字。

  2. 位置贡献分析：考虑第p位（从右往左，0-indexed）对总和的贡献。第p位的权重是10^p，每个数字l到r在这一位上出现的次数相同。

  3. 单位贡献计算：

    • 数字i（l ≤ i ≤ r）在第p位出现的次数：(r-l+1)^(k-1)
    • 第p位所有数字的贡献：10^p × (l+l+1+...+r) × (r-l+1)^(k-1)
    • 其中 (l+l+1+...+r) = (r-l+1)×(l+r)/2

  4. 总和公式推导：

    • 对所有位置求和：∑(p=0 to k-1) 10^p × digit_sum × count
    • 提取公共因子：digit_sum × count × ∑(p=0 to k-1) 10^p
    • 几何级数求和：∑(p=0 to k-1) 10^p = (10^k - 1) / 9

  5. 最终公式：

    总和 = (l+r)×(r-l+1) / 2 × (r-l+1)^(k-1) × (10^k - 1) / 9

注意事项：

  • 使用快速幂计算大指数
  • 使用模运算逆元计算除法
  • 所有运算都要取模防止溢出

代码实现

class Solution {
public:
    int sumOfNumbers(int l, int r, int k) {
        const long long MOD = 1000000007;
        
        if (l > r || k == 0) return 0;
        
        long long digitSum = (long long)(l + r) * (r - l + 1) / 2 % MOD;
        long long count = modPow(r - l + 1, k - 1, MOD);
        long long pow10k = modPow(10, k, MOD);
        long long numerator = (pow10k - 1 + MOD) % MOD;
        long long inv9 = modInverse(9, MOD);
        
        long long result = digitSum * count % MOD;
        result = result * numerator % MOD;
        result = result * inv9 % MOD;
        
        return result;
    }
    
private:
    long long modPow(long long base, long long exp, long long mod) {
        long long result = 1;
        base %= mod;
        while (exp > 0) {
            if (exp & 1) {
                result = result * base % mod;
            }
            base = base * base % mod;
            exp >>= 1;
        }
        return result;
    }
    
    long long modInverse(long long a, long long mod) {
        return modPow(a, mod - 2, mod);
    }
};

class Solution:
    def sumOfNumbers(self, l: int, r: int, k: int) -> int:
        MOD = 10**9 + 7
        
        if l > r or k == 0:
            return 0
        
        def mod_pow(base, exp, mod):
            result = 1
            base %= mod
            while exp > 0:
                if exp & 1:
                    result = (result * base) % mod
                base = (base * base) % mod
                exp >>= 1
            return result
        
        def mod_inverse(a, mod):
            return mod_pow(a, mod - 2, mod)
        
        digit_sum = (l + r) * (r - l + 1) // 2 % MOD
        count = mod_pow(r - l + 1, k - 1, MOD)
        pow10k = mod_pow(10, k, MOD)
        numerator = (pow10k - 1) % MOD
        inv9 = mod_inverse(9, MOD)
        
        result = (digit_sum * count) % MOD
        result = (result * numerator) % MOD
        result = (result * inv9) % MOD
        
        return result

public class Solution {
    public int SumOfNumbers(int l, int r, int k) {
        const long MOD = 1000000007;
        
        if (l > r || k == 0) return 0;
        
        long digitSum = (long)(l + r) * (r - l + 1) / 2 % MOD;
        long count = ModPow(r - l + 1, k - 1, MOD);
        long pow10k = ModPow(10, k, MOD);
        long numerator = (pow10k - 1 + MOD) % MOD;
        long inv9 = ModInverse(9, MOD);
        
        long result = digitSum * count % MOD;
        result = result * numerator % MOD;
        result = result * inv9 % MOD;
        
        return (int)result;
    }
    
    private long ModPow(long baseNum, long exp, long mod) {
        long result = 1;
        baseNum %= mod;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                result = result * baseNum % mod;
            }
            baseNum = baseNum * baseNum % mod;
            exp >>= 1;
        }
        return result;
    }
    
    private long ModInverse(long a, long mod) {
        return ModPow(a, mod - 2, mod);
    }
}

var sumOfNumbers = function(l, r, k) {
    const MOD = 1000000007;
    
    // Sum of digits in range [l, r]
    let digitSum = 0;
    for (let i = l; i <= r; i++) {
        digitSum = (digitSum + i) % MOD;
    }
    
    // Number of choices per position
    const choices = r - l + 1;
    
    // Total numbers = choices^k
    const totalNumbers = modPow(choices, k, MOD);
    
    // Each digit appears in each position: totalNumbers * choices^(k-1) / choices = totalNumbers * choices^(k-2) times
    // But we need to count how many times each digit appears across all positions
    
    // For each position, each digit appears totalNumbers / choices times
    // Across k positions, each digit contributes: digitSum * (totalNumbers / choices) * (10^0 + 10^1 + ... + 10^(k-1))
    
    const timesPerPosition = totalNumbers * modInverse(choices, MOD) % MOD;
    
    // Sum of 10^0 + 10^1 + ... + 10^(k-1) = (10^k - 1) / 9
    let geometricSum;
    if (k === 1) {
        geometricSum = 1;
    } else {
        const pow10k = modPow(10, k, MOD);
        geometricSum = (pow10k - 1 + MOD) % MOD;
        geometricSum = geometricSum * modInverse(9, MOD) % MOD;
    }
    
    const result = digitSum * timesPerPosition % MOD * geometricSum % MOD;
    return result;
};

function modPow(base, exp, mod) {
    let result = 1;
    base = base % mod;
    while (exp > 0) {
        if (exp % 2 === 1) {
            result = (result * base) % mod;
        }
        exp = Math.floor(exp / 2);
        base = (base * base) % mod;
    }
    return result;
}

function modInverse(a, mod) {
    return modPow(a, mod - 2, mod);
}
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(log k)
空间复杂度O(1)

说明：

  • 时间复杂度主要来自快速幂运算，需要计算 (r-l+1)^(k-1) 和 10^k，复杂度为 O(log k)
  • 空间复杂度为常数级别，只使用了几个变量存储中间结果