ABC310 Eの解き方 - tsugaru’s blog

落ちているやり方と違っていたので

仮にf(i,j)が一瞬でわかったとして、長さは10⁶であるから、 f(i,j)の全ての通りを足す時間(10¹²)はない。

ここで、例えばあるiについて $\sum_i f(i,j) = g(j)$ がすでにわかっていたとする。このとき、g(i-1)との間に何か関係があれば、 10⁶に対して2乗しないで済み、他のg(i)を定数で求められるので、合計が10⁶で求まる。

ここで、

$\sum_{i=1}^{N} \sum_{j=i}^{N} f(i,j) = \sum_{j=0}^{N} \sum_{i=1}^{j} f(i,j)$

である。

$\begin{align} g(j) &= \sum_{i=1}^{j} f(i,j) \\ g(j+1) &= \sum_{i=1}^{j+1} f(i,j+1) \\ &= \sum_{i=1}^{j}f(i,j+1) + f(j+1,j+1) \\ &= \sum_{i=1}^{j} f(i,j)nand A_{j+1} + A_{j+1} \end{align}$

ここで、 $x \ nand \ y = 1 - xy$ であるから、

$\begin{align} g(i+1) &= \sum_{i=1}^{j} (1-f(i,j)*A_{j+1}) + A_{j+1} \\ &= j-A_{j+1}*\sum_{i=1}^{j}f(i,j) + A_{j+1} \\ &= j-A_{j+1}*g(j) + A_{j+1} \end{align}$

以上を用いて作成したプログラムは以下の通り。

n=int(input())
s=input()
g_old=int(s[0])
r=g_old
for j in range(1,n):
    g_old=j-int(s[j])*g_old + int(s[j])
    r+=g_old
print(r)