Pythonで文字列として与えられた数値の全部分文字列の合計を求める方法

問題概要

文字列形式で与えられた数値 s のすべての部分文字列を整数とみなし、その合計を求めます。答えは非常に大きな値になる可能性があるため、10⁹+7 で割った余りを返します。

たとえば入力が s = "268" の場合、部分文字列は "2"、"6"、"8"、"26"、"68"、"268" の6つで、合計は 2 + 6 + 8 + 26 + 68 + 268 = 378 となります。

考え方：各桁の「寄与」に着目する

部分文字列をすべて列挙して足し合わせる素朴な方法では、部分文字列の数が O(n²) 個に達し、文字列が長いと現実的な時間で処理できません。そこで、「ある1桁が合計に何回・どの位で現れるか」を直接計算する方法を使います。

左から i 番目(0始まり)の桁を d、文字列の長さを n とすると、d の寄与は次のように整理できます。

• d は、終了位置が i 以降のすべての部分文字列に含まれる。
• 開始位置の候補は 0〜i の (i+1) 通りある。
• 終了位置との距離に応じて、d は 1の位・10の位・100の位… として現れる。

これをまとめると、d の合計への寄与は次の式で表せます。

d × (i + 1) × (1 + 10 + 100 + … + 10^(n−1−i))

括弧内の 1 + 10 + 100 + … は 1、11、111、… と続くレピュニット(1が並ぶ数)です。ループごとに B を「B = B × 10 + 1」で更新すれば、この値を順番に求められます。

アルゴリズムの手順

• M := 10^9 + 7(剰余を取るための定数)
• B := 1(レピュニット)、res := 0(合計)
• i を n−1 から 0 まで降順に繰り返す。
  • res := (res + int(s[i]) × B × (i + 1)) mod M
  • B := (B × 10 + 1) mod M
• res を返す。

Pythonでの実装例

def solve(s):
    M = 10 ** 9 + 7
    B = 1     # レピュニット(1, 11, 111, ...)
    res = 0   # 部分文字列の合計
    for i in range(len(s) - 1, -1, -1):
        res = (res + int(s[i]) * B * (i + 1)) % M
        B = (B * 10 + 1) % M
    return res

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

入力

"268"

出力

378

動作の流れ(s = "268" の場合)

• i = 2(桁「8」)：res = 8 × 1 × 3 = 24、B は 11 に更新
• i = 1(桁「6」)：res = 24 + 6 × 11 × 2 = 156、B は 111 に更新
• i = 0(桁「2」)：res = 156 + 2 × 111 × 1 = 378

最終的に 378 が返され、手計算の結果と一致します。

計算量

文字列を一度走査するだけなので、時間計算量は O(n)、追加メモリは O(1) で済みます。桁数の多い数値文字列でも高速に処理できるのが、この方法の大きな利点です。