【AtCoder Regular Contest 067 E】Grouping

mrsrz 3月 04, 2020

动态规划。

题目大意：

有 $n$ 个人，编号 $1\sim n$，现在要将它们分组，满足：

每组的人数要在 $[A,B]$ 之间。
人数为 $i$ 的组要么没有，要么数量在 $[C,D]$ 之间。

求方案数。

题解：

考虑枚举组别以及选这个组别的人数，进行 dp。

令 $f_{i,j}$ 表示当前考虑到一组 $i$ 人，有 $j$ 个人已经分组了。

枚举 $k$ 表示一组 $i$ 人需要选 $k$ 组，不难得到转移：

$f_{i,j}=\sum_{k=C}^{D}f_{i-1,j-i\cdot k}\binom{n-j+i\cdot k}{i\cdot k}\cdot\frac{(i\cdot k)!}{(i!)^k}\cdot \frac 1 k$

由于 $i\cdot k$ 不超过 $D$，所以枚举 $k$ 是一个调和级数，故总时间复杂度 $O(n^2\log n)$。

Code：

#include<cstdio>
const int md=1e9+7,N=1007;
typedef long long LL;
int n,A,B,C,D,F[N][N],fac[N],iv[N];
inline int pow(int a,int b){
    int ret=1;
    for(;b;b>>=1,a=(LL)a*a%md)if(b&1)ret=(LL)ret*a%md;
    return ret;
}
int main(){
    scanf("%d%d%d%d%d",&n,&A,&B,&C,&D);
    for(int i=*fac=1;i<=n;++i)fac[i]=(LL)fac[i-1]*i%md;
    iv[n]=pow(fac[n],md-2);
    for(int i=n-1;~i;--i)iv[i]=(i+1LL)*iv[i+1]%md;
    F[A-1][0]=1;
    for(int i=A;i<=B;++i)
    for(int j=0;j<=n;++j){
        int&f=F[i][j];f=F[i-1][j];
        for(int k=C,g=pow(iv[i],C);k<=D&&k*i<=j;++k,g=(LL)g*iv[i]%md){
            int L=n-j+k*i;
            f=(f+(LL)F[i-1][j-k*i]*fac[L]%md*iv[k*i]%md*iv[L-k*i]%md*fac[k*i]%md*g%md*iv[k])%md;
        }
    }
    printf("%d\n",F[B][n]);
    return 0;
}