2026-06-25：给定范围内 K 位数字之和。用go语言，给定三个整数 l、r、k。
我们要考虑所有恰好有 k 位的整数，这些整数的每一位数字都是这样选出来的：
对每一位，从区间 [l, r]（包含端点）的数字中独立随机选择一个作为该位的数字；如果 [l, r] 内包含 0，那么允许出现前导零（因此不要求最高位不能为 0）。
把所有符合条件的 k 位数全部列出，然后计算它们的总和。
由于结果可能非常大，请对 1000000007 取模，返回最终结果。
0 <= l <= r <= 9。
1 <= k <= 1000000000。
输入： l = 5, r = 5, k = 10。
输出： 555555520。
解释：
5555555555 是唯一一个由范围 [5, 5] 内 k = 10 位数字组成的有效数字。
总和为 5555555555 % 1000000007 = 555555520。
题目来自力扣3855。
一、数学推导分步详解（对应代码sumOfNumbers公式来源）
步骤1：计算单一位的数字平均值
区间 [l, r] 数字总和：Sdigit=l+(l+1)+…+r=(l+r)⋅m2S_{digit} = l + (l+1) + … + r = \\frac{(l+r)\\cdot m}{2}Sdigit=l+(l+1)+…+r=2(l+r)⋅m
其中 m=r−l+1m = r-l+1m=r−l+1，代表每一位可选数字总个数。
每位数字的期望（平均取值）：
avg=Sdigitm=l+r2avg = \\frac{S_{digit}}{m} = \\frac{l+r}{2}avg=mSdigit=2l+r
步骤2：拆分k位数的位权贡献（核心思想）
一个k位数，从右到左各位权值依次是：100, 101, 102, …, 10k−110^0,\\ 10^1,\\ 10^2,\\ …,\\ 10^{k-1}100, 101, 102, …, 10k−1
所有合法数字总和 = 每一位单独贡献之和，每一位贡献相互独立，可分开计算再相加。
单一位（固定某一位置，比如第t位，权值10t10^t10t）的总贡献
所以单个位置总贡献：
contribt=(l+r)⋅m2⋅mk−1⋅10tcontrib_t = \\frac{(l+r)\\cdot m}{2} \\cdot m^{k-1} \\cdot 10^tcontribt=2(l+r)⋅m⋅mk−1⋅10t
所有k个位置总贡献求和
总和 Total=∑t=0k−1contribtTotal = \\displaystyle \\sum_{t=0}^{k-1} contrib_tTotal=t=0∑k−1contribt
提取公共因子 (l+r)⋅m⋅mk−12\\displaystyle \\frac{(l+r)\\cdot m \\cdot m^{k-1}}{2}2(l+r)⋅m⋅mk−1：
Total=(l+r)⋅m⋅mk−12⋅∑t=0k−110tTotal = \\frac{(l+r)\\cdot m \\cdot m^{k-1}}{2} \\cdot \\sum_{t=0}^{k-1} 10^tTotal=2(l+r)⋅m⋅mk−1⋅t=0∑k−110t
等比数列求和：∑t=0k−110t=10k−110−1=10k−19\\displaystyle \\sum_{t=0}^{k-1}10^t = \\frac{10^k – 1}{10 – 1} = \\frac{10^k – 1}{9}t=0∑k−110t=10−110k−1=910k−1
代入总和公式：
Total=(l+r)⋅m⋅mk−12⋅10k−19Total = \\frac{(l+r)\\cdot m \\cdot m^{k-1}}{2} \\cdot \\frac{10^k – 1}{9}Total=2(l+r)⋅m⋅mk−1⋅910k−1
合并分母：2×9=182 \\times 9 = 182×9=18
Total=(l+r)⋅m⋅(10k−1)⋅mk−1⋅118Total = (l+r) \\cdot m \\cdot (10^k – 1) \\cdot m^{k-1} \\cdot \\frac{1}{18}Total=(l+r)⋅m⋅(10k−1)⋅mk−1⋅181
步骤3：模意义下除法转换为乘法逆元
模数 mod=1e9+7 是质数，根据费马小定理：
对不被mod整除的x，x−1≡xmod−2(modmod)x^{-1} \\equiv x^{mod-2} \\pmod{mod}x−1≡xmod−2(modmod)
原式除以18等价于乘以18的模逆元：pow(18, mod−2)pow(18,\\ mod-2)pow(18, mod−2)。
同时 10k−110^k-110k−1 可能为负数（模运算下），所以加mod再取模保证正数：(pow(10,k)−1+mod)%mod(pow(10,k)-1+mod)\\%mod(pow(10,k)−1+mod)%mod。
最终模运算公式（和代码完全对应）：
Total(modmod)=[(l+r)⋅m(modmod)]⋅[(10k−1+mod)(modmod)](modmod)⋅inv18(modmod)⋅[mk−1(modmod)](modmod)
\\begin{align}
Total \\pmod{mod}
&= \\Big[(l+r) \\cdot m \\pmod{mod}\\Big] \\\\
&\\cdot \\Big[(10^k – 1 + mod) \\pmod{mod}\\Big] \\pmod{mod} \\\\
&\\cdot inv_{18} \\pmod{mod} \\\\
&\\cdot \\Big[m^{k-1} \\pmod{mod}\\Big] \\pmod{mod}
\\end{align}
Total(modmod)=[(l+r)⋅m(modmod)]⋅[(10k−1+mod)(modmod)](modmod)⋅inv18(modmod)⋅[mk−1(modmod)](modmod)
其中：
m=r−l+1m=r-l+1m=r−l+1，inv18=pow(18,mod−2)inv_{18}=pow(18, mod-2)inv18=pow(18,mod−2)，powpowpow 为模快速幂。
二、代码执行分步流程（以输入l=5,r=5,k=10举例）
阶段1：预处理常量与基础变量
阶段2：分项逐个计算（按公式乘法顺序）
分项A：(l+r)(l + r)(l+r)
5+5=105+5=105+5=10。
分项B：(10k−1)mod mod(10^k – 1) \\mod mod(10k−1)modmod，负数修正
调用快速幂 pow(10, 10) 算出 101010^{10}1010；
计算 1010−110^{10}-11010−1，再加mod避免负数：(pow(10,10)−1+mod)%mod(pow(10,10)-1+mod)\\%mod(pow(10,10)−1+mod)%mod，得到9999999999。
分项C：18的模逆元
程序每次计算都会调用 pow(18, mod-2)，预先算出18在模1e9+7下的乘法逆元，记为inv18。
分项D：mk−1mod modm^{k-1} \\mod modmk−1modmod
m=1，任意次幂结果都是1，调用快速幂 pow(1, 9) 得到1。
阶段3：逐项模乘合并结果
严格按顺序连续相乘，每一步都对mod取模，防止数值溢出：
最终得到总和模mod的值 555555520。
阶段4：输出结果
打印合并后的模值，匹配样例输出。
三、核心工具：快速幂pow(x, n)详细执行逻辑
函数作用：快速计算 xnmod modx^n \\mod modxnmodmod，n可高达1e9，二进制分解幂次。
- 若当前n二进制最低位为1（n%2==1）：把res = res * x % mod，把当前底数乘入结果；
- 更新底数：x = x * x % mod（底数平方，对应二进制高位）；
以样例中pow(10,10)为例：
10二进制是1010，循环仅执行log₂10≈4次，无需循环10次。
四、总时间复杂度、额外空间复杂度分析
1. 时间复杂度
程序内一共调用3次快速幂：
其余加减乘、变量赋值都是O(1)常数操作。
logmod\\log modlogmod 是固定常量可忽略，总时间复杂度：
O(logk)\\boldsymbol{O(\\log k)}O(logk)
2. 额外空间复杂度
总额外空间复杂度：
O(1)\\boldsymbol{O(1)}O(1)（常数空间）
Go完整代码如下：
package main
import (
"fmt"
)
const mod = 1_000_000_007
func pow(x, n int) int {
res := 1
for ; n > 0; n /= 2 {
if n%2 > 0 {
res = res * x % mod
}
x = x * x % mod
}
return res
}
func sumOfNumbers(l, r, k int) int {
m := r – l + 1
return (l + r) * m * (pow(10, k) – 1 + mod) % mod * pow(18, mod–2) % mod * pow(m, k–1) % mod
}
func main() {
l := 5
r := 5
k := 10
result := sumOfNumbers(l, r, k)
fmt.Println(result)
}
Python完整代码如下：
# -*-coding:utf-8-*-
MOD = 1_000_000_007
def pow_mod(x, n):
"""快速幂取模"""
res = 1
while n > 0:
if n % 2 == 1:
res = res * x % MOD
x = x * x % MOD
n //= 2
return res
def sum_of_numbers(l, r, k):
m = r – l + 1
# (l + r) * m * (10^k – 1) * inv(18) * m^(k-1) mod MOD
return (l + r) * m % MOD * (pow_mod(10, k) – 1 + MOD) % MOD * pow_mod(18, MOD – 2) % MOD * pow_mod(m, k – 1) % MOD
def main():
l = 5
r = 5
k = 10
result = sum_of_numbers(l, r, k)
print(result)
if __name__ == "__main__":
main()
C++完整代码如下：
#include <iostream>
using namespace std;
const long long MOD = 1000000007LL;
long long pow_mod(long long x, long long n) {
long long res = 1;
while (n > 0) {
if (n % 2 == 1) {
res = res * x % MOD;
}
x = x * x % MOD;
n /= 2;
}
return res;
}
long long sumOfNumbers(long long l, long long r, long long k) {
long long m = r – l + 1;
long long result = (l + r) % MOD;
result = result * m % MOD;
result = result * ((pow_mod(10, k) – 1 + MOD) % MOD) % MOD;
result = result * pow_mod(18, MOD – 2) % MOD;
result = result * pow_mod(m, k – 1) % MOD;
return result;
}
int main() {
long long l = 5;
long long r = 5;
long long k = 10;
long long result = sumOfNumbers(l, r, k);
cout << result << endl;
return 0;
}
