Q4. Sum of K-Digit Numbers in a Range

📘 題目敘述

給你三個整數 l、r、k。考慮所有恰好由 k 個數字組成，且每位數都從 [l, r] 選出的整數，求這些數字總和（對 10^9 + 7 取模）。

條件限制

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

🧠 解題思路（最後TLE）

我把總和拆成每一位的貢獻，並用三個關鍵量：

• each = (l+r) * (r-l+1) / 2：單位數可選數字總和
• every = 111...1（k 個 1）：位權總和
• comb = (r-l+1)^(k-1)：固定某位時其餘位的組合數

最後用 ans = each * every * comb（過程全程取模）得到答案；但因為我用線性迴圈跑到 k，在大資料會 TLE。

所有變數

• ans：最後答案
• c：模數 10^9 + 7
• each：l..r 的總和
• every：k 個 1 組成的位權和
• comb：(r-l+1)^(k-1)

🪜 主要流程步驟

1. 先算 each

用等差級數公式計算數字範圍總和。

2. 建出 every

用 every = every * 10 + 1 迴圈建出 k 位 1。

3. 算 comb

用乘法迴圈累積 (r-l+1)^(k-1)。

4. 相乘得到答案

將三者相乘並取模。

5. 回傳 ans

回傳最終結果。

⏱️ 複雜度

• 時間複雜度：O(k)
• 空間複雜度：O(1)

💻 程式碼實作

class Solution {
public:
    int sumOfNumbers(int l, int r, int k) {
        long long ans = 0;
        const int c = 1000000007;
        int each = (l + r) * (r - l + 1) / 2;
        long long every = 0;
        long long comb = 1;
        for (int i = 1; i <= k; i++) {
            every = every * 10 + 1;
            every %= c;
            if (i > 1) {
                comb *= r - l + 1;
                comb %= c;
            }
        }
        ans = every * each;
        ans %= c;
        ans *= comb;
        ans %= c;
        return ans;
    }
};

🔗 題目連結

https://leetcode.com/contest/biweekly-contest-177/problems/sum-of-k-digit-numbers-in-a-range/