Competitive Programing Typical 90 Problem day5

プログラミング

Day 5. 

It is a really hard problem for me, but I manage to write codes and grasp the meaning of them.

There are 3 answers. Each of them has own perspective. 1st one is Digit DP, 2nd one is matrix exponentiation, last one is Doubling.

Code is below.

1st one.

#1st solution
N, B, K = map(int,input().split())
C = list(map(int, input().split()))
#入力を準備する。
MOD = 10**9 + 7
dp = [[0 for b in range(B)] for n in range(N) ]
#動的計画法のかごを用意する
for j in range(K):
  dp[0][C[j]%B] += 1
#最初の条件（状態）、1桁目
for i in range(N-1):
  for j in range(B):
    for k in range(K):
      new = (10 * j + C[k]) % B
      dp[i+1][new] += dp[i][j]
      dp[i+1][new] %= MOD
print(dp[N-1][0])  
  • 桁ごとに考える問題。
  • 今回のように、いくつもの要素があって、その組み合わせ、または、数（数も離散的な一つ一つの塊として見れる）その組み合わせを順々にいろいろ計算したいと気に、動的計画法が使える。
  • 詳しくはこちら。
    • 問題を複数の部分問題に分解して考えたいときに出来る。
    • ボトムアップ（小さいものから組み立てる）
    • トップダウン（大きなものをばらしていく）
      • この場合、メモ化再帰が使える。
        • 再帰はばらすときに使える。
    • 大概はこういうこと。
      • 問題は複雑なことが多い。
      • でも、バラバラにすると、一つ一つの問題が簡単に解ける場合がある。
      • 生物も、一つ一つの事象が簡単で、まとまると複雑に見える、ということではないか？

2nd one.

#2nd solution
N, B, K = map(int,input().split())
C = list(map(int, input().split()))
#入力を準備する。
MOD = 10**9 + 7


import numpy as np
A = [[0 for i in range(B)] for j in range(B)]
#隣接行列のかごを用意する
for i in range(B):
  for k in range(K):
    A[(i*10 + C[k])%B][i] += 1

#隣接行列を用意する。行と列に遷移前後のBでの余りを保持
#その組み合わせが、隣接行列になる。
def bit(n):
  bit_digit = []
  while n > 0:
    if n%2 == 1:
      bit_digit.append(1)
    else:
      bit_digit.append(0)
    n //= 2
  #一桁目は2で割ったあまり
  #二桁目は4で割って2余るか
  return bit_digit
  #ここは正しい

def Dot(M1,M2,n):
  #行列の積を定義する。
  M = [[0] * n for _ in range(n)]
  for i in range(n):
    for j in range(n):
      for k in range(n):
        M[i][j] += M1[i][k] * M2[k][j]
        M[i][j] %= MOD
        #足し合わせる、MODで割る
  return M

bit_N = bit(N)
#N桁なので、N個の隣接行列をかければよい
#　　これは最初が0だから。
#〇〇桁なので、べき乗の準備をする。
#Nを2進数に直す
bit_length = len(bit_N)


def Power_Matrix(M3,k,n):
  P = [[0] * n for _ in range(n)]
  for i in range(n):
    P[i][i] = 1
  for j in range(k):
    #Ｍ３の（ｊ）乗の部分
    if bit_N[j]==1:
      P = Dot(P,M3,n)
      #二進法で桁が１なら×
    M3 = Dot(M3, M3, n)
    #かける行列を二乗する。
  return P

Answer = Power_Matrix(A,bit_length,B)
print(Answer[0][0])
  • Fibonacci数列みたいに、足し方、隣接行列が決まっているものは、工夫できる。
  • 隣接行列を最初にべき乗で求めていく。
  • こういう 10 = 2 + 8, 30 = 2 + 4 + 8 + 16のような分解を利用して、べき乗を処理していく（掛けていく）のを、繰り返し二乗法という。

3rd one.

#3rd solution
N, B, K = map(int,input().split())
C = list(map(int, input().split()))
#入力をとる
MOD = 10**9 + 7
LOG = 64

def Multiply(list1,list2,number):
  res = [0] * B
  for i in range(B):
    for j in range(B):
      res[(i * number + j) % B] += list1[i] * list2[j]
      res[(i * number + j) % B] %= MOD
  return res
#リスト同士の掛け算を定義する。
#Numberによって、掛け算の仕方が変化する。
#リスト2つとNumberを変数にとる関数

ten = [10] * LOG
for i in range(1, LOG):
  ten[i] = (ten[i-1] * ten[i-1]) %B
#これで、10のべき乗の余りのリストが出来る。
#順番に、1, 10 , 100, 1000 ,....

Matrix = [[0] * B for _ in range(LOG)]
#2**n桁の余りの行列のかごを用意する
for k in range(K):
  Matrix[0][C[k] % B ] += 1
  #1桁目はC[k]％Bを割り当てていく

for i in range(1,LOG):
  Matrix[i] = Multiply(Matrix[i-1], Matrix[i-1], ten[i-1])
  #Matrixのi個目と、i-1個の階差行列がten[i-1]、というイメージ
  #このmatrixは、2のi乗桁上がると、何通りになるかを掛ける行列

answer = [0] * B
answer[0] = 1
for i in range(LOG):
  if N &(1<<i):
    answer = Multiply(answer, Matrix[i], ten[i])
    #2のi乗の桁が1なら、10進法の2のi乗桁分を足す
    #そのために、MatrixとAnswerの積（さっき定義した）をかける

print(answer[0])
#あまり0の部分を印刷する。
  • 2ndまでは、遷移すること、変化させていく方法に着目していた。
    • でも、行列同士の掛け算は、O(B^3)かかるのでシンドイ。
  • 今回は、2桁と2桁の完成形同士の合成、というように、すでに出来上がったものを組み合わせて、4桁のような、大きなものを作る
    • これが、O(B^2)で出来てうれしい。
  • このように、2**i回目の結果から2**(i+1)回目の結果を得る方法を、ダブリングという。
  • 高速フーリエ変換とか、きたまさ法、というのがこれに使えるらしいが、今は踏み込まないことにする。

バイバイ！