桁DPと呼ばれるらしい。
ある数以下の整数を対象とするとき、上の桁から見ていって、境界ギリギリかどうかによって取り得る値の範囲が変わる。
例えば、$N=4567$とする。
次の桁の範囲が限られるか、自由かで、分けて状態を持つ。
桁DPでよく出てくる構造は、以下。
$DP[i][j][k]=$上位 $i$ 桁まで考慮して、次の桁の範囲は $[j=0:限られない/1:限られる]$ で、桁和の合計(mod D) が $k$ である数字の個数
ただ今回は単純なので、こんなんでもいい。
$DP[i][k]=$上位 $i$ 桁まで考慮して、次の桁の範囲が限られないもので、桁和の合計(mod D) が $k$ である数字の個数
$DP2[i]=$ 上位 $i$ 桁までの $N$ の桁和(mod D)
M - Candies と同じく範囲加算が必要なので、累積和を用いる。数字の範囲が「自由」か「制限」かで分類する。
$i$ 桁目は0~9の任意の値を取る。
$DP[i-1][s]=c$($i-1$ 桁目までの和が $s$ のものが $c$ 個ある)時、愚直にやると
DP[i][s+0 mod D] += c DP[i][s+1 mod D] += c DP[i][s+2 mod D] += c ... DP[i][s+9 mod D] += c
となる。遅いので、いもす法を使って高速化する。(累積和を取るのは後で)
DP'[s+ 0] += c DP'[s+10] -= c
これを各 $s=0..(D-1)$ について行う。
$i-1$ 桁目までが $N$ と一致し、$i$ 桁目が $N_i$(Nのi桁目の数字)より小さいような数が、これになる。
$i-1$ 桁目までのパターン数は($N$ と一致してないといけないので)当然1通り。その桁和をsとして、遷移は
DP[i][s+0 mod D] += 1 DP[i][s+1 mod D] += 1 ... DP[i][s+(Ni-1) mod D] += 1
となる。上と同様に累積和を使う。
DP'[s+0] += 1 DP'[s+Ni] -= 1
ここまでの各sについて処理後、DP[i] = DP'の累積和 として、遷移が完了する。
$i-1$ 桁目までが $N$ と一致し、$i$ 桁目も $N_i$ と一致する数が、これになる。
パターン数は1通りとわかっているのでDP配列に状態数を管理する必要は無い。 上記の「制限→自由」の際の更新に用いるので桁和だけ更新しておく。
$DP2[i]=DP2[i-1] + N_i % D$
DP配列における桁和の状態数は、mod D をとるため本来は $D$ 個(0~(D-1))でいいのだが、 累積和による更新をやりやすくするため配列としては $D+10$ の大きさのものを作り、D以上の部分は累積和を取った後に移動させる。
最終的な答えは $DP[Nの桁数][0]$ だが、これには0
も入っている。「1以上 $N$ 以下の整数」の個数を求めるので、1引く。
また、$N$ そのものは最後までDP配列で管理されないので、もし $N$ の桁和が $D$ の倍数だった場合は1足す。
from itertools import accumulate k = input() d = int(input()) dp = [0] * (d + 10) dp2 = 0 MOD = 10 ** 9 + 7 for c in k: c = int(c) for e in range(d - 1, -1, -1): dp[e + 10] -= dp[e] dp[dp2] += 1 dp[dp2 + c] -= 1 dp = list(accumulate(dp)) for e in range(9, -1, -1): dp[e] += dp[d + e] dp[d + e] = 0 for e in range(d): dp[e] %= MOD dp2 = (dp2 + c) % d ans = dp[0] - 1 # exclude '000..0' if dp2 == 0: ans += 1 print(ans % MOD)
N = 4 S = <>< 1 < 3 > 2 < 4 3 < 4 > 1 < 2 など5個が条件を満たす
DP自体は割と普通だが、持たせる情報に「なるほど」という発想が必要。
まず愚直な思いつきが、
$DP[i][j][S]=i$ 番目の数字まで確定し、$p_i=j$ であり、未使用の整数の組が $S$ であるような状態の数
必要な情報を考えると、次に来る数字を決めるに当たって前の数字($p_i$)は必要だし、 $p_i$ が同じでも残る整数の組によって次に来れる数の個数は異なってくる。
だが、これはどう考えても $S$ が管理できる状態数にならない。
次のようにすると良いらしい。
$DP[i][j]=i$ 番目の数字まで確定し、$p_i$ が、($p_i$を含めた)残る整数の中で $j$ 番目に小さいものであるような状態の数
各項が全て異なる数列の、隣り合う数字の大小を考慮するだけなら、数字の順位のみが重要となる。
の2つは、その後の状態数は全く同じになるため、区別する必要が無い。
$k=N-i$($i$を含めない残りの数字の個数)とする。また、数字の順位を0-indexとする。
k| 9 k-1| 7 1+3+5+..7 | ... 2| 5 1+3+5 1| 3 1+3 0| 1 1 ---+------------------ i i+1
k| 9 k-1| 7 9 | ... 2| 5 9+7+.. 1| 3 9+7+..+5 0| 1 9+7+..+5+3 ---+------------------ i i+1
最終的に $DP[N]$ の長さは1になるので、$DP[N][0]$ が答え。
from itertools import accumulate n = int(input()) s = input() dp = [1] * n MOD = 10 ** 9 + 7 for i in range(n - 1): if s[i] == '>': dp.reverse() dp = list(accumulate(dp[:-1])) dp.reverse() else: dp = list(accumulate(dp[:-1])) for j in range(len(dp)): dp[j] %= MOD print(dp[0])
bitDP
$SG[s]=$集合 $s$ に属するウサギが全て同一グループに入る時のスコア
$DP[s]=$集合 $s$ に属するウサギだけでグループ分けして得られる最大スコア
$SG$ は、事前計算する。
たとえば $s=0011010$ の時、最下位で立っているビット(2) とそれ以外(4,5) に分けて考えると、$SG[0011010] = SG[0011000] + a_{2,4} + a_{2,5}$ のように計算できる。
$DP$ の計算が肝。
$s$ の部分集合 $p$ を全探索する。$p$ を同一グループに入れ、残り($s \setminus p$)の最適な分け方はそれより前に計算したDPの値を参照し、その合計の最大が $DP[s]$ となる。
$\displaystyle DP[s]=\max_{p \subseteq s}(SG[p]+DP[s \setminus p])$
$s$ の部分集合 $p$ はどのように得たらいいか。愚直に $0~2^N$ を回して $s$ の部分集合か1つずつ確かめるのはさすがにTLE。
減算とマスクを用いると、上手く全ての部分集合を得られる。
g = h = 0b011010 while h: print(f'{h:06b}') h = (h - 1) & g # => # 011010 # 011000 # 010010 # 010000 # 001010 # 001000 # 000010
$s$ の小さい方から $DP$ を埋めていき、$s=2^N-1$ の時が答え。
n = int(input()) a = [list(map(int, input().split())) for _ in range(n)] same_groups = [0] * (1 << n) for i in range(1, 1 << n): k = i rb = k & -k ri = rb.bit_length() - 1 ar = a[ri] k ^= rb val = same_groups[k] while k: pb = k & -k val += ar[pb.bit_length() - 1] k ^= pb same_groups[i] = val dp = [0] * (1 << n) for grp in range(1 << n): g = grp while g: dp[grp] = max(dp[grp], same_groups[g] + dp[grp ^ g]) g = (g - 1) & grp print(dp[-1])
全方位木DPと呼ばれるらしい。
木DPは適当な1頂点を根とするが、全方位木DPは、全ての頂点を根として考えなければならない場合に使う(と思う)
まずは普通に適当な頂点を根としてDFSなどで木DPする。
その後、2回目のDFSを行う。 親から頂点 $v$ に移動するとき、「$v$ が根になった場合の答えを求めるのに必要な情報」を与えながら移動する。 この値は根から累積的に計算できるようにしておく。
$DP1[v]=$(頂点1を根として)頂点 $v$ 以下の部分木で、$v$ を黒く塗るようなパターン数
探索方法は何でもよいが、頂点1から再帰的にDFSで求めるとする。
頂点 $v$ の子の1つを$u$とする。
計$DP1[u]+1$通りの塗り分け方が、$u$ 以下の部分木に対して可能である。同様に$v$の各子供に対して求め、掛け合わせた数が、$DP1[v]$となる。
$\displaystyle DP1[v] = \prod_{u \in vの子供} (DP1[u]+1)$
$v=1$ の時の出力すべき答えは、最終的な $DP1[1]$ に入っている。根が指定されていればこれで良かった。
同様にDFSで頂点1から探索するとする。
頂点 $v$ の親を $p$ とする。
また「もし親子関係が逆転して、$p$ が $v$ の子になったら、$p$ 以下の部分木を塗り分けるパターン数$a$」が $p$ から伝えられているとする。
2回目の遷移では、以下のことを行いたい。
1つめは簡単で、$DP1[v] \times a$ がそれになる。 要は$DP1$では、$v$から伸びる枝のうち $p$ に伸びるもののパターン数だけが考慮できてなかったのが、 $p$から伝えられたので、情報が補完された。
2つめは、少し厄介。 率直には「$v$ から伸びる枝のうち $u$ に伸びるものだけを掛け合わせないパターン数」を伝えれば良い。
$\displaystyle \frac{DP1[v] \times a}{DP1[u]+1}$ をすればよい……かと思うが、値はとても大きくなるため、$M$ で割った値が入っている。 しかし、この $M$ はいつものように素数とは限らないため、モジュラ逆数が使えない。要は割り算が出来ない。
ならば、$a \times \prod_{c \in vの子供\setminus\{u\}} (DP1[c]+1)$ のように、$u$を除いた子のDP1の値を逐一かけてもよいが、 $v$ にめっちゃ多くの子がぶら下がっていた場合、全ての子でやると $O(子の数^2)$ の計算量が必要となり、特殊な入力でTLEする。
このように、割り算が出来ない状況下で「ある集合から、1つだけを除いた積」を求めたい場合は、前後双方からの累積積を求めておくと良い。
i 1 2 3 4 5 v 2 3 5 7 11 ---------------------------------- 累積積pf 1 2 6 30 210 2310 累積積pb 2310 1155 385 77 11 1
前後の'1'は計算上の便宜的なものとする。 $i=3$ を除いた積を求めたい場合は、pf[2] と pb[4] を掛け合わせればよい。6×77=462となる。 (実際のindexは異なるが、イメージとして)
各頂点についての子の累積積は、1回目の探索の際についでに求めたが、2回目の探索時にその頂点についてだけ構築した方がメモリに優しいね。
これで、$u$に、$v$ が部分木となった場合のパターン数を伝えられ、連鎖的に全頂点の答えが求められた。
import sys sys.setrecursionlimit(100000) def dfs1(v, p): val = 1 pre_mul = [1] rev_mul = [] for c in links[v]: if c == p: pre_mul.append(val) rev_mul.append(1) continue res = 1 + dfs1(c, v) val *= res val %= m pre_mul.append(val) rev_mul.append(res) dp[v] = val for i in range(len(rev_mul) - 2, -1, -1): rev_mul[i] *= rev_mul[i + 1] rev_mul[i] %= m rev_mul.append(1) pre_muls[v] = [pre_mul, rev_mul] return val def dfs2(v, p, a): dp[v] = dp[v] * a % m pmv = pre_muls[v] for i, c in enumerate(links[v]): if c == p: continue pmc = pmv[0][i] * pmv[1][i + 1] % m pmc = pmc * a % m dfs2(c, v, pmc + 1) n, m = map(int, input().split()) links = [[] for _ in range(n)] dp = [0 for _ in range(n)] pre_muls = [None for _ in range(n)] for line in sys.stdin.readlines(): x, y = map(int, line.split()) x -= 1 y -= 1 links[x].append(y) links[y].append(x) dfs1(0, None) dfs2(0, None, 1) print('\n'.join(map(str, dp)))