ABC288 F問題 Integer Division

具体例で考える

入力例 2の 5915 は、次のように計算されます。

$N$ 桁の数は、切れ目を入れられる部分が $N-1$ 個あり、それぞれについて切れ目を入れる/入れないのどちらかになるため、[2^{N-1}] 通りの掛け算の和を求めることになります。 $N$ は大きな数になりうる( $N \leqq 2\times 10^5$ )ので、すべての掛け算を計算して和を求めるのは困難です。
そこで、桁を増やしていく動的計画法で考えていきます。

動的計画法をどのように行うか

下から3桁の 915 は、次のように計算されます。

この前に 5 を加えて4桁にします。5 と 9 の間に切れ目が入るケースは、

からわかるように、3桁の結果に 4桁目の数字の 5をかけた値になります。
残りは5 と 9 の間に切れ目が入らないケースで、整理すると、

となります。下 $n$ 桁の計算結果を $dp(n)$ と表すと、4桁目の数を $a_4$ として
$dp(4) = a_4 \times dp(3) + dp(3) + a_n \times 10^1\times dp(2) + a_n \times 10^2 \times dp(1) + a_n \times 10^3 \\ = dp(3)+ a_4 \times \left(dp(3) + 10^1\times dp(2) + 10^2 \times dp(1) + 10^3\right)$

これを参考にすると、一般項として
$P(n) = dp(n-1) + 10\times P(n-1)$
$dp(n) = dp(n-1) + a_n\times P(n)$
と表すことができます。

コード例 (Julia)

function solve()

  MOD_ = 998244353

  # 入力
  readInt()  =  parse(Int,readline())

  # 入力データ
  N = readInt()
  S = readline()

  P = 1
  dp = parse(Int,S[N])

  for i = N-1:-1:1
    P = dp + 10 * P
    P %= MOD_
    dp = dp + parse(Int,S[i]) * P
    dp %= MOD_
  end

  println(dp)

end  # function solve

# main
solve()