CodeForces Round #736 Div. 2 E - The Three Little Pigs 問題概要
整数$ N が与えられる。今から投げられる$ Q個のクエリを処理せよ。$ i\ (1 \leq i \leq Q)個目のクエリは以下のようである。
整数$ xが与えられるので$ \sum_{i = 0}^{N}\ _{3i}\mathrm{C}_{x}を求めよ。
解法
$ dp[a][b] = \sum_{i = 0}^{N - 1}\ _{3i + b}\mathrm{C}_{a} と定義する。すると、求めるものはdp[x][0] + 3N C xとなる。
すると、以下の$ 3つの式が成り立つ。
$ dp[a][0] + dp[a][1] + dp[a][2] = \sum_{i = 0}^{3N - 1}\ _{i}\mathrm{C}_{a} = _{3N}\mathrm{C}_{a + 1}
$ dp[a][1] = dp[a][0] + dp[a - 1][0]
$ dp[a][2] = dp[a][1] + dp[a - 1][1] = dp[a][0] + dp[a - 1][0] + dp[a - 1][1]
$ 1つ目の式は定義から明らか。
$ 2,3個目の式は、$ _{n}\mathrm{C}_{r} = _{n - 1}\mathrm{C}_{r} + _{n - 1}\mathrm{C}_{r - 1}を使うと証明できる。
なので、$ 1つ目の式に$ 2,3個目の式を代入して
$ 3 \times dp[a][0] + 2 \times dp[a- 1][0] + dp[a - 1][1] = _{3N}\mathrm{C}_{a + 1}
$ dp[a][0] = \frac{1}{3}(_{3N}\mathrm{C}_{a + 1} - 2 \times dp[a - 1][0] - dp[a - 1][1])
これと$ dp[0][0] = dp[0][1] = dp[0][2] = N から全体で$ \mathrm{O}(N + Q)で解くことができた。