📘 題目敘述
給你整數
l、r、k，考慮所有恰有
k 位，且每位皆從
[l,r] 選出的數字，求總和對 1e9+7 取模。
條件限制
0 <= l <= r <= 91 <= k <= 10^9
🧠 解題思路（最後TLE）
把答案拆成每一位貢獻：each 是可選數字總和、comb
是固定某位時其餘位組合數、every 是位權和
111...1。最後相乘得到答案。
所有變數
ans：最後答案c：模數each：範圍總和every：位權和comb：組合數
🪜 主要流程步驟
1. 算 each
用等差級數公式。
2. 算 every
迴圈建出 k 個 1 的數字（取模）。
3. 算 comb
迴圈算出 (r-l+1)^(k-1)。
4. 相乘
依序乘上 each 與 comb。
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/problems/sum-of-k-digit-numbers-in-a-range/