UVALive 7143 Room Assignment（组合数学+DP）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目链接

参考自：http://www.cnblogs.com/oyking/p/4508260.html

题意

n个人，其中有k对双胞胎.现有m间房间，每间房间有容量ci问分配房间的方案数。

分析

设dp[i][j]为已经放满了第i个房间之后，所剩下的双胞胎的对数还有j对，然后对于i+1间房，我们可以从剩余的j对中选择出a对，每对双胞胎只是放一个就好，然后又从j-a对双胞胎中选b对全部放进去，然后再从剩余的sum-j2中选择c[i]-a-2b个放进i+1个房间里面,这样的话就能得到转移方程， dp[i+1][j-a-b]=dp[i][j]C(j,a)C(j-a,b)C(sum-j2,c[i]-a-b2) ;然后组合数就用逆元去算就ok了。时间复杂度是O（（mk）³）

#include <cstdio>

#include <algorithm>

#include <iostream>

#include <cstring>

using namespace std;

typedef long long LL;

const int MAXN = ;

const int MOD = 1e9 + ;

int inv[MAXN], fact[MAXN];

int _inv(int x) {

    if(x == ) return ;

    return LL(MOD - MOD / x) * _inv(MOD % x) % MOD;

}

void init(int n = ) {

    fact[] = ;

    for(int i = ; i <= n; ++i)

        fact[i] = fact[i - ] * LL(i) % MOD;

    for(int i = ; i <= n; ++i)

        inv[i] = _inv(fact[i]);

}

LL comb(int a, int b) {

    if(a < b) return ;

    return LL(fact[a]) * inv[b] % MOD * LL(inv[a - b]) % MOD;

}

int dp[][];

int c[];

int T, n, m, k;

int mulmul(LL a, LL b, LL c, LL d) {

    return a * b % MOD * c % MOD * d % MOD;

}

void update_add(int &a, int b) {

    a += b;

    if(a >= MOD) a -= MOD;

}

int solve() {

    memset(dp, , sizeof(dp));

    dp[][k] = ;

    for(int i = , sum = n; i < m; ++i) {

        for(int r = ; r <= k; ++r) if(dp[i][r]) {

            if(sum <  * r) break;

            for(int a = ; a <= r; ++a) {

                for(int b = ; b + a <= r; ++b) {

                    if(c[i + ] - a -  * b < ) break;

                    int t = mulmul(dp[i][r], comb(r, a), comb(r - a, b), comb(sum -  * r, c[i + ] - a -  * b));

                    update_add(dp[i + ][r - a - b], t);

                }

                if(i == m - ) break; /// if i = m - 1 then a must be zero

            }

        }

        sum -= c[i + ];

    }

    return dp[m][];

}

int main() {

    init();

    //printf("%d\n", comb(10, 1));

    scanf("%d", &T);

    for(int t = ; t <= T; ++t) {

        scanf("%d%d%d", &n, &m, &k);

        for(int i = ; i <= m; ++i) scanf("%d", &c[i]);

        printf("Case #%d: %d\n", t, solve());

    }

}