ARC067 E. Grouping
問題
1からNまで番号がついたN人がいる。
- どのグループも、そのグループに含まれる人数がA人以上B人以下
- i人のグループの数をF_iとしたとき、F_iは0またはC以上D以下
このようなグループ分けが何通りあり得るかmod 10^9+7で求めよ。
制約
- 1 <= N <= 10^3
- 1 <= A <= B <= N
- 1 <= C <= D <= N
解法
解説、解説放送の方法。
問題がややイメージしにくいので、具体事例を考えてみる。
例えば、「(1),(2),(5),(3,4),(6,7)」のようなグループ分けだった場合は、
| グループ内の人数 | グループの個数 |
|---|---|
| 0人 | 0グループ |
| 1人 | 3グループ |
| 2人 | 2グループ |
| 3人 | 0グループ |
のようになっている。
A,Bは表左の人数に関する条件、CDは表右のグループ数に関する条件を表しており、条件を満たすならこのグループ分けは1カウントに数え上げられる。
数え上げなのでdpを考えてみると、「グループ内の人数」と「それまでの確定した人数」を状態にした以下のようなdpが考えられる。
dp[i][j] := i人以下のグループのみでグループを作ったとして、その合計人数がj人であるようなグループ分けの通り数
漸化式を考えると、i-1までが求められていたとして、i人グループを作ることを考えると、グループをx個作る場合は、
dp[i][j] = Σ_x f(i,j,x) * dp[i-1][j-i*x]
ここでf(i,j,x)は「残っている人で、i人グループをx個作る場合のグループ分けの数」。
これはiとjとxでO(N^3)っぽく見えるが、xはグループの個数で、iが大きくなるほど作れるグループ数は少なくなり、xはj/i個までしか作れないので、これはO(N^2 logN)となる。
( O(N + N/2 + N/3 + ...) = O(N logN) )
したがって、f()が十分に高速に求められれば間に合う。
f(i,j,k)を求める。
N人中すでに(j-i*x)人はグループになっているので、残りの(N-j+i*x)人からi人グループをx個作ることになる。
各人は番号がついていて区別できるので、並びも考慮するイメージで、「(N-j+i*x)人からi*x人を並べる通り数 (N-j+i*x)_P_(i*x)」から、重複分の「グループ内での並びは関係ない分 ( i! )^x」と「グループ自体の並びも関係ない分 x!」を割ってあげた以下の式になる。
f(i,j,k) = (N-j+i*x)_P_(i*x) / { ( i! )^x * x! } = (N-j+i*x) ! / { (N-j)! * (i!)^k * x! }
MOD階乗、MOD累乗、MOD逆元でこれを求めてあげればよい。
