Pythonで文字列として指定された数値のすべての部分文字列の合計を見つけるプログラム

文字列形式の数値があり、sのすべての部分文字列の合計を見つける必要があるとします。答えは非常に大きい可能性があるため、10 ^ 9+7を法とする結果を返します。

したがって、入力がs ="268"の場合、サブストリングが "2"、 "6"、 "8"、 "26"、 "68"、および "268"であるため、出力は378になります。合計は378です。 。

これを解決するには、次の手順に従います-

• M：=10 ^ 9 + 7
• sum_val：=0
• B：=1
• res：=0
• s-1から0までの範囲サイズのiの場合、1ずつ減らします。
  • res：=（res + s [i] * B *（i + 1）の桁値）mod M
  • sum_val：=sum_val-s[i]の桁値
  • B：=（B * 10 + 1）mod M
• return 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