板刷计划:ARC067

传送门:https://atcoder.jp/contests/arc067/tasks/arc067_c

题目大意:

将n个人划分成若干组。每一组大小 $sz\in [A,B]$ ,每个大小出现的次数要么为0次，要么为 $[C,D]$ 次.现在给你n,A,B,C,D,问你不同的方案数。两个方案视作不同当且仅当存在两个人，它只在某一个方案中存在于同一个组中. $n <=1e3$

例如: 7 1 3 1 2

只能分成: 2 + 2 + 3, 方案数为105种.

先考虑这个问题如何计数:通过观察样例不难发现，就是组合数相乘。对于大小相同的组，要除一个全排列打消顺序。

不难利用动态规划: $dp(i,j)代表把i个人最多划分成的组的大小为j的方案数.$ 形成前缀和的形式。我们枚举从i个人中选 $k \in [C,D]$ 个大小为j的组的方案数：

$dp(i,j) = dp(i,j-1)+\sum_{k=C}^{D}\frac{i!}{(j!)^k*(i-kj)!} * \frac{1}{A_{k}^{k}}* dp(i - k j,j-1)$

注意:式子右边的常系数的推导如下:

$C_{n}^{x}*C_{n - x}^{x}*...*C_{n - (k-1)x}^{x} =\frac{n!}{x!*(n-x)!} *\frac{(n-x)!}{x!*(n-2x)!} * ... * \frac{(n - (k-1)x)!}{x!*(n-kx)!} =v$

$\frac{n!}{(x!)^k *(n-kx)!}$ . 由于组之间无差别，所以还需要乘一个 $\frac{1}{A_{k}^{k}}$ 打消组间顺序.

写起来是三重循环的递推,但不是n^3.大约分析如下:(估算复杂度上界)

$\sum_{i=1}^n \sum_{j=A}^B\sum_{k=C}^{min(D,\frac{i}{j})}1 = \sum_{i=1}^n \sum_{j=A}^B \frac{i}{j}=\sum_{i=1}^n i*lni=n^2logn$

注：第二步到第三步利用了调和级数定理.

复杂度上界为: $\Theta (n^2logn)$

AC代码：https://atcoder.jp/contests/arc067/submissions/17136658