0, 1, 2 - Construction

2 secs 1024 MB
bayashiko's icon bayashiko

左から値を1つずつ確定させていくことを考えます。
i1i-1 番目まで確定し、次に ii 番目の値を決める時、既に確定している数列としてあり得るものは 3i13^{i-1} 通りあるのでこれを全部持つことは出来ませんが、 ii 番目にどの値を置けるかの判定に必要なのは直前の M1M-1 個の値の情報だけなので、以下のようなdpが出来ます。
dp[i][j]=dp[i][j] = ii 番目まで確定し、直前の M1M-1 個の数列が jj であるような数列のうち今のところ条件を満たしているものの個数
計算量は O(N3M)O(N3^M) です。