ARC067 Grouping I

---

题目链接

https://arc067.contest.atcoder.jp/tasks/arc067_c

题意

把n个人分组,每组的人数必须在A-B之间.并且如果有一个组有i(i>0)个人,那么有i个人的组数要在C-D之间．问有多少种分组方案

分析

• 用dp[i][j]来表示从n个人中取出ｉ个来，分组后每组人数最多ｊ的方案数
• 转移的时候枚举恰好j个人的小组的数量．

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
const int maxn=1050;
ll dp[maxn][maxn];
ll Pow(ll x,ll n){
    ll ans=1,base=x%MOD;
    while(n){
        if(n&1) ans=ans*base%MOD;
        base=base*base%MOD;
        n>>=1;
    }
    return ans;
}
ll fact[maxn],inv[maxn];
void init(){
    fact[0]=1;
    for(int i = 1; i < maxn; ++i) fact[i]=fact[i-1]*i%MOD;
    inv[maxn-1]=Pow(fact[maxn-1],MOD-2);
    for(int i = maxn-2; i >= 0; --i) inv[i]=inv[i+1]*(i+1)%MOD;
}
int main(){
    init();
    int n,A,B,C,D;
    scanf("%d%d%d%d%d", &n,&A,&B,&C,&D);
    for(int i = 0; i <= B; ++i) dp[0][i]=1;
    for(int i = 1; i <= n; ++i){
        for(int j = A; j <= B; ++j){
            if(i==0) dp[i][j]=1;
            else{
                ll &u=dp[i][j];
                u=dp[i][j-1];
                for(int k = C; k <= D&&i-j*k>=0; ++k){
                    u+=dp[i-j*k][j-1]*fact[n-i+j*k]%MOD*inv[j*k]%MOD*inv[n-i]%MOD*fact[j*k]%MOD*inv[k]%MOD*Pow(inv[j],k)%MOD;
                    u%=MOD;
                }
            }
        }
    }
    cout << dp[n][B] << endl;
    return 0;
}