F - Integer Division Editorial by kyopro_friends
- index は 0-indexed とする。
- 文字列 \(S\) の \(i\) 文字目を \(S_i\) とおき、\(i\) 文字目以降 \(j\) 文字目より前からなる部分文字列を \(S[i:j]\) とおく。例えば \(S\) が
abcdef
のとき、\(S_2\) はc
であり、\(S[2:4]\) はcd
である。 - 数字及び数字のみからなる文字列を、それを整数とみなしたときの値と同一視する。
- \(f(i)\) を \(X[0:i]\) に対する答えとする。ただし、\(f(0)=1\) と定める。求めるものは \(f(N)\) である。
- \(f(0)=1\) と定めるのは、次の式で \(i=k\) のケースの場合分けを除くためである。
文字列の末尾から遡って初めて \(\times \) が登場する位置で場合分けすることで次の式を得る。
\(\displaystyle f(k)=\sum_{i=1}^{k}f(k-i)S[k-i:k]\\ =\sum_{i=1}^{k}f(k-i)\sum_{j=1}^{i}S_{k-j}10^{j-1}\\ =\sum_{j=1}^{k}\sum_{i=j}^{k}f(k-i)S_{k-j}10^{j-1}\\ =\sum_{j=1}^{k}S_{k-j}10^{j-1}\sum_{i=j}^{k}f(k-i)\\ =\sum_{j=1}^{k}S_{k-j}10^{j-1}\sum_{i=0}^{k-j}f(i)\\ =\sum_{j=0}^{k-1}S_{j}10^{k-j-1}\sum_{i=0}^{j}f(i)\)
ここで、\(g(j)=\sum_{i=0}^{j}f(i)\) として \(f\) の累積和 \(g\) を定めると、\(k+1>1\) のとき、
\(\displaystyle f(k+1)=\sum_{j=0}^{k}S_j10^{k-j}g(j)\\ =S_{k}g(k)+\sum_{j=0}^{k-1}S_j 10^{k-j}g(j)\\ =S_{k}g(k)+10f(k)\)
となる。したがって、以下の漸化式により、\(O(N)\) で \(f(N)\) を求めることができる。
\(f(k)=\begin{cases} 1 & k=0\\ S_0 & k=1 \\ S_{k-1}g(k-1)+10f(k-1) & k>1 \end{cases}\)
\(g(k)=\begin{cases} 1 & k=0 \\ g(k-1)+f(k) & k>0 \end{cases}\)
posted:
last update: