ABC129 E - Sum Equals Xor

当初，書こうと思っていたわけではないので，文章の方は適当である．図が多分説明してる．．．

一番，難しいのは dp table の最初の値じゃない？と思った． とりあえず，一桁の時を考えると欲しい answer はこうなる．dp table の最初の値がわかれば解ける人は多そうなので，この情報で帰ってもいいと思う．

ABC129 E. dp 最初

まずは，確定の時の初期値である 0(dp[0][0]) の事は考えず，未確定の時の初期値である 1(dp[1][0]) をどう使うかを考える．最上桁の値が 1 の時と 0 の時で確定するかしないか，次の候補の数が異なる．

ABC129 E. dp 候補の抜き出し

これは，2桁以上を考えるとわかるが，確定した値をどう使うかを考える．候補は [0, 0], [0, 1], [1, 0] の3つあるので，それぞれを3倍する必要がある．

ABC129 E. dp 確定した値の継続

2桁以上でも上手くいくかを考える．

ABC129 E. 2桁以上の時

ここまでくれば反映させるだけなので，コードを書くと

L = input()
modulo = 10**9+7

dp = [[0] * (len(L)+1) for i in range(2)]
dp[1][0] = 1
  
for i in range(len(L)):
  if L[i] == "1":
    dp[0][i+1] = dp[1][i]
    dp[1][i+1] = dp[1][i] * 2
  else:
    dp[1][i+1] = dp[1][i]
  
  dp[0][i+1] += (3 * dp[0][i])
  dp[0][i+1] %= modulo
  dp[1][i+1] %= modulo


print((dp[0][-1]+dp[1][-1]) % modulo)

でした．print 時の modulo 忘れてて大変だった．．． 色んな人のコードを見たけど，普通は i の index と 0, 1 の index が逆らしい．