本戦中にはなんとか解けたけど、通り数計算まわりで無限にハマってつらくなった問題。
こんなハマり方はしないようにしたい...。
問題概要
1からまでの番号付きの個のブロックがある。
を満たすを選び、以上以下のブロックを消すことを考える。
この時、各で消すか消さないかの組み合わせは通り考えられる。
この組み合わせの中で個のブロック全て消せる組み合わせは何通り存在するか?で割った余りで答えよ。
制約
解法
dpで解く。
以下のような、想定解法よりシンプルなdpを考えてた。
番号iのブロックまで全てのブロックを消した時の通り数
このdpではについて、 を から求める。
計算の考え方として、番号jのブロックが残っている時に、ブロックjからブロックiまでを一気に消す場合(つまり、で消される場合) の通り数を考えて値を伝搬させる。
との関係に応じて以下の2つのケースに分け、その和を計算することでを求める。
そして最後まで計算した後、を解として出力すればよい。
1. の場合
番号jのブロックが残っている時に、ブロックjからブロックiを一気に消すためには、少なくとも
のいずれかで消す必要があり、消せないケースはこれらのいずれも行わなかった場合のみである。
そのため、通りの消し方が存在する。
よって、をに加えればよい。
2. の場合
まず、ブロックjからブロックiまでを一気に消すためには、少なくとも
のいずれかで消す必要があり、これで消せる通り数はとなる。
またの場合では、番号jのブロックを消さずに、番号j+1から番号iまでのブロックを消す通り数も考慮する必要がある。
この通り数はとなるについて考慮した通りとなる。
よって、 を に加えればよい。
実装
計算量は
提出コード(PyPy3): Submission #4300115 - 全国統一プログラミング王決定戦本戦
N, K = map(int, input().split()) MOD = 10**9 + 7 dp = [0]*(N+1) dp[0] = 1 # (2**k % MOD) の O(N^2) の前計算 pw2 = [1]*(N**2+1) for i in range(N**2): pw2[i+1] = pw2[i] * 2 % MOD for i in range(K+1, N+1): r = 0 for j in range(i): b = 1 if j < i-K: b = pw2[(i-j-K-1)*(i-j-K)//2] * (pw2[j+1]-1) % MOD else: b = pw2[i-K] - 1 r += dp[j] * b % MOD dp[i] = r % MOD print(dp[N])