ARC107 D - Number of Multisets
この解法、結構時間かかるので流石に本番では選べないか……？
$N \leq 3000$ なので $Ο(N^2 log N)$ は通しにくい($Ο(N^3)$ でも枝刈すると通るらしいけど……)。
なるべく情報 $2$ 個で通らないだろうか？
考えたこと
- $\frac{1}{2^i}$ を選ぶ部分和 DP はキリがない
- 部分和といっても総和 $K$ にしか興味がないのでどうにかそれ以外の情報は捨てられないだろうか？→そもそも総和 $K$ の状態で集合の中身を弄る感じにしたい
- $1$ を分解して $\frac{1}{2} \times 2$ にすると長さが $1$ 増加してしまう。→長さ $1, 2, \ldots, N$ のそれぞれを考える DP に出来るか？
- $3$. における漸化式を考えると、$\frac{1}{2^i}$ を $\frac{1}{2^{i+1}}$ に分解するには $\frac{1}{2^i}$ がいくつあるかを知りたい。→求め方は $2$ 通り。
- $\frac{1}{2^{i-1}}$ を分解した結果生じた $\frac{1}{2^{i}}$ の個数を保持する
- $\frac{1}{2^{i-1}}$ をいくつ分解したかを保持する
- $4$-$1$. を吟味→$\frac{1}{2^i}$ を $\frac{1}{2^{i+1}}$ に分解すると $\frac{1}{2^{i+1}}$ の個数は $2$ の倍数になって飛び飛びになる。恐らくダメそう
- $4$-$2$. を吟味→計算量度外視なら出来そう。恐らく $Ο(N^3)$ になる。$Ο(N^2)$ にならないだろうか？→ $4$-$1$. ではダメだが、$4$-$2$. では累積和が出来るかも。ここで $4$-$2$. の採用が確定する。
- 情報を整理する。
- $dp[i][j] =$ 要素数 $i$ 個の状態から遷移して、 $j$ 個で総和 $K$ が達成できる多重集合の種類数
7 ~ 8 が大分ぶっ飛んでいるのでより詳細に説明する。
だいたいの方針としては「ある数字 $f$ を $\frac{f}{2}$ に分解する」ことを DP 上で漸化式として表現しようとしている。
そのため、初期状態は $dp[0][K] = 1$ となる。
そのうえで、複数個の分解を行うことを累積和でどうにかして高速に処理しようとした。つまり、ある状態から分解して得られる状態を一括で遷移するようにするのだ。
しかし、分解できる数は $1$ 種類のみであり、そうなるように処理しなければ論理が破綻する。そのため「今の状態で分解が有効な数がいくつあるか？」を保持しなくてはならなくなる。
例えば、${1, 1, 1}$ を分解して ${1, 1, \frac{1}{2}, \frac{1}{2}}$ を得たとする。次に分解が有効なのは $\frac{1}{2}$ のみであり、$1$ を分解することは出来ないようにしたい。なぜなら、そのような分解は ${1, 1, 1}$ から ${1, \frac{1}{2}, \frac{1}{2}, \frac{1}{2}, \frac{1}{2}}$ に分解することと同値なためである。
ここで、分解が有効な数が具体的に何なのかまでは保持しなくてよいことに注目されたい。それが幾つであろうと $\frac{1}{2}$ をかけた数 $2$ 個に分解されるのみである。
よって状態は要素数が以前いくつだったか、そして分解によっていくつになったかだけに圧縮できてしまうのではないかと考える。
次に、累積和について考える。
要素数が $i$ である状態から $dp[i][i+1, i+2, \ldots, i+x]$ に遷移するようにすると、気持ちとしては前の次元のほうが固定されるので考えやすい。
これで $dp[i]$ から $dp[?]$ に遷移する前に累積和すれば正当な値になる。
最後に漸化式と初期状態を考える。
初期状態は先ほども述べたように $dp[0][K] = 1$ となるが、追加があるので後述する。
かつて要素数 $i$ だった状態から、なんらかの数を分解して要素数 $j$ になったとする。この状態で分解が有効な要素はいくつあるだろうか？
例：
${1, 1, 1}$ を分解して ${1, 1, \frac{1}{2}, \frac{1}{2}}$ を得たとする。次に分解が有効なのは $\frac{1}{2}$ のみである。この場合は、分解が有効な要素は $2$ 個ある。
ここで逆に、分解が無効な要素はいくつあるかを考える。
$i$ 個から $j$ 個に遷移したということは差分が $j-i$ 個であるので、$j-2(j-i)$ を解けば解が得られる。解は $2i-j$ となる。
ここから分解が有効な要素数を求められる。$j-(2i-j) = 2j-2i$ 個となる。
ここで、$x$ 個の分解が無効な数と $y$ 個の分解が有効な数について、全ての分解個数を試すと分解結果の個数は区間 $[x+y+1, x+2 \times y]$ になる。
このことから、分解個数の最大値は $2i-j+2(2j-2i)$ となり、整理すると $3j-2i$ となる。
ちなみに $x+y$ とは $j$ のことなので、累積和を考慮した漸化式は以下の通り。
$$dp[j][j+1] += dp[i][j]$$
$$dp[j][a] -= dp[i][j] (a=3j-2i+1, 0 \leq a \leq N)$$
しかし、唯一この漸化式が狂う場合が存在する。$i=0$ の場合である。
この場合に対処するために、$i=K$ の場合を最初に埋め込んでおく。
初期条件(追加分を含む、累積和を考慮)：
$$dp[0][K]=1$$
$$dp[K][K+1]=1$$
$$dp[K][2K+1]=-1(2K+1 \leq N)$$
以上、これを求めた結果の
$$Σ_{i=0}^{N} dp[i][N]$$
が解となる。
