
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。
区间 [l, r] 数字总和:
其中 ,代表每一位可选数字总个数。
每位数字的期望(平均取值):
一个k位数,从右到左各位权值依次是: 所有合法数字总和 = 每一位单独贡献之和,每一位贡献相互独立,可分开计算再相加。
总和 提取公共因子 :
等比数列求和: 代入总和公式: 合并分母:
模数 mod=1e9+7 是质数,根据费马小定理:
对不被mod整除的x,
原式除以18等价于乘以18的模逆元:。
同时 可能为负数(模运算下),所以加mod再取模保证正数:。
最终模运算公式(和代码完全对应):
mod = 1000000007;。
调用快速幂 pow(10, 10) 算出 ;
计算 ,再加mod避免负数:,得到9999999999。
程序每次计算都会调用 pow(18, mod-2),预先算出18在模1e9+7下的乘法逆元,记为inv18。
m=1,任意次幂结果都是1,调用快速幂 pow(1, 9) 得到1。
严格按顺序连续相乘,每一步都对mod取模,防止数值溢出:
打印合并后的模值,匹配样例输出。
函数作用:快速计算 ,n可高达1e9,二进制分解幂次。
以样例中pow(10,10)为例: 10二进制是1010,循环仅执行log₂10≈4次,无需循环10次。
程序内一共调用3次快速幂:
其余加减乘、变量赋值都是O(1)常数操作。 是固定常量可忽略,总时间复杂度:
总额外空间复杂度: (常数空间)
.
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)
}

.
# -*-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()
.
#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;
return0;
}

·
我们相信人工智能为普通人提供了一种“增强工具”,并致力于分享全方位的AI知识。在这里,您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。
·