ARC107 D. Number of Multisets
問題
正整数N, Kが与えられる。
以下の条件を全て満たす有理数の多重集合は何種類存在するか、mod 998244353で求めよ。
- 多重集合の要素数はNで、要素の総和はK
- 多重集合の要素はすべて、1,1/2,1/4,1/8, ... すわなち、1/2^iのいずれか
制約
- 1 <= K <= N <= 3000
解法
最初にN個の要素に1がK個分埋まった状態「1 1 1 1 ... 1 x x x x ... x」からスタートして、何回か今ある要素を1/2倍した2つに分解する操作をしてN個分埋めたときの状態数を考える。
ただし、重複しないように、1, 1/2, 1/4, ...の順に大きい値から分解していく。
まず、O(N * K^2)を考える。
1から考えると、1がK個あり、このうちk個(k=1～K)を分解し、残りのK-k個を確定させると考える。
すると、これは、N-(K-k)個の要素で2*k個の1/2が埋まった状態を考えるのと同じになるので再帰的に求められる。
したがって、
calc(K,N) := N個の要素のうち、K個が最初に埋まっている場合、上記の操作をしてできる最終的な状態数
とすると、
calc(K,N) = Σ_{k=1}^{k=K} calc(2*k, N-(K-k))
と書ける。
しかし、O(K)かけてしまっているため間に合わない。
ここで別の再帰構造を考えると、「0個確定させる場合(全部分解する場合)」と「(一番値の大きい)1つだけ確定させる場合」だけで考えられる。
0個確定させる場合＝全部分解する場合は、k=Kの場合で、calc(2*K,N)になる。
1つだけ確定させる場合は、N-1個の要素でK-1個分埋まった状態calc(N-1,K-1)になり、1つ小さい問題になる。
したがって、各calc(K,N)でO(1)になるので、メモ化再帰等でO(NK)で求められる。
