51Nod－1453－抽彩球

ACM模版

描述

題解

很好地一道題，可以用dp解（Two），也可以用插空法（One），然而，由于dp實在不好了解，我也沒能徹悟，是以這裡介紹一下插空法。

從後往前推，把第k種顔色放在最後一個，剩下的k球，有C（剩餘的空位置，k球總數-1）種放置方法，然後讨論第k-1種，以此類推下去……由于組合比較大，需要用乘法逆元，也可以直接套Lucas。

至于dp的解法，我看得不是太懂，具體的思路可以去大牛光速小子0511的部落格裡看，��，暫時了解不了，我太笨了……

代碼

One：

#include <stdio.h>

#define LL long long

const LL MOD =  + ;
const int MAXN =  + ;
const int MAXM =  + ;

int n;
int a[MAXN];
LL fac[MAXM];

LL ppow(LL x, LL y)
{
    LL c = ;
    while (y)
    {
        if (y & )
        {
            c = c * x % MOD;
        }
        y >>= ;
        x = x * x % MOD;
    }
    return c;
}

LL work(LL m, LL i)
{
    return ((fac[m] % MOD) * (ppow((fac[i] * fac[m-i]) % MOD, MOD - ) % MOD)) % MOD;
}

int main()
{
    fac[] = ;
    for(int i = ; i < MAXM; i++)
    {
        fac[i] = (fac[i - ] * i) % MOD;
    }
    LL ans = ,sum = ;
    scanf("%d", &n);
    for(int i = ; i<= n; i++)
    {
        scanf("%d", a + i);
        sum += a[i];
    }
    for(int i = n; i >= ; i--)
    {
        ans *= work(sum - , a[i] - );
        ans %= MOD;
        sum -= a[i];
    }
    printf("%lld\n", ans);

    return ;
}
           

Two：

#include <iostream>

using namespace std;

typedef long long ll;

const int MOD =  + ;
const int MAXN =  + ;

int k;
ll res, sum;
int c[MAXN];
long long C[MAXN][MAXN];

void init()
{
    for (int i = ; i < MAXN; i++)
    {
        for (int j = ; j <= i; j++)
        {
            if (j ==  || j == i)
            {
                C[i][j] = ;
            }
            else
            {
                C[i][j] = (C[i - ][j - ] + C[i - ][j]) % MOD;
            }
        }
    }
    return ;
}

void input()
{
    scanf("%d", &k);
    sum = ;
    for (int i = ; i <= k; i++)
    {
        scanf("%d", &c[i]);
        c[i]--;
    }
    return ;
}

void solve()
{
    ll empty = ;   //  目前有多少空位
    res = ;

    for (int i = ; i <= k; i++)
    {
        res = (res * C[empty + c[i] - ][c[i]]) % MOD;
        empty = empty + c[i] + ;
    }
    cout << res << endl;
    return ;
}

int main()
{
    init();
    input();
    solve();

    return ;
}