Python程序：查找给定字符串数字的所有子字符串的总和

假设我们有一个字符串格式的数字，我们需要找到字符串 s 的所有子字符串的总和。答案可能非常大，因此返回结果模 10^9+7。

所以，如果输入类似 s = "268"，那么输出将是 378，因为子字符串是 "2"、"6"、"8"、"26"、"68" 和 "268"，总和是 378。

为了解决这个问题，我们将遵循以下步骤：

• M := 10^9 + 7
• sum_val := 0
• B := 1
• res := 0
• 对于 i 从 s 的大小 - 1 到 0，递减 1，执行：
  • res :=(res + s[i] 的数字值 * B *(i + 1)) mod M
  • sum_val := sum_val - s[i] 的数字值
  • B := (B * 10 + 1) mod M
• 返回 res

示例

让我们看看下面的实现来更好地理解：

def solve(s):
   M = 10 ** 9 + 7
   sum_val = 0
   B = 1
   res = 0
   for i in range(len(s) - 1, -1, -1):
      res = (res + int(s[i]) * B * (i + 1)) % M
      sum_val -= int(s[i])
      B = (B * 10 + 1) % M
   return res

s = "268"
print(solve(s))

输入

"268"

输出

378

Arnab Chakraborty

更新于: 2021年10月7日

395 次浏览

开启你的 职业生涯

通过完成课程获得认证

立即开始