HDU 4248 A Famous Stone Collector (dp)

제목:
색깔이 다른 돌을 드릴게요. 돌을 한 줄로 세우면 총 몇 가지의 배열법이 있는지 물어보세요. 수량에 따라 돌을 상황으로 보고 위치마다 돌의 색깔이 똑같아요. 같은 상황으로 봐요.
문제 해결 방법:
먼저 k개의 돌에 대해 x가지의 다른 색깔의 돌이 있고 각각의 색깔의 돌은 각각 k개가 있다. 그러면 이 k개의 돌은 한 줄로 늘어서서 모두 k가 있다!( k1!*k2!*k3!..kx!)종 상황수, 그래서 dp[i][j]를 설정하면 전 i종 색깔의 돌을 모두 j개의 돌을 선택한 상황을 나타낼 수 있다.
상태 이동 방정식은 dp[i][j+k]=dp[i-1][j]/k!,여기/k!바로 곱하기 k!의 역원.

#include <stdio.h>
#include <string.h>
typedef __int64 ll;

const int mod = 1000000007;
const int maxn = 10000 + 10;

ll exgcd(ll a, ll b, ll &x, ll &y) {
    if(!b){
        x = 1; y = 0;
        return a;
    }
    ll ret = exgcd(b, a%b, y, x);
    y -= a/b*x;
    return ret;
}

ll inv(ll n, ll mod) {
    ll x, y, d = exgcd(n, mod, x, y);
    return (x%mod + mod)%mod;
}

ll fac[maxn], ff[maxn];
void init(int n) {
    fac[0] = 1;
    ff[0] = inv(1, mod);
    for(int i = 1;i <= n; i++) {
        fac[i] = fac[i-1]*i%mod;
        ff[i] = inv(fac[i], mod);
    }
}

ll dp[105][10005];
int a[111];
int main() {
    init(10000);
    int n, cas = 1;
    while(scanf("%d", &n) != -1) {
        for(int i = 1;i <= n; i++)
            scanf("%d", &a[i]);
        int tot = 0;
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        for(int i = 1;i <= n; i++) {
            for(int j = 0;j <= tot; j++) {
                for(int k = 0;k <= a[i]; k++) {
                    dp[i][j+k] += dp[i-1][j]*ff[k];
                    if(dp[i][j+k] >= mod)   dp[i][j+k] %= mod;
                }
            }
            tot += a[i];
        }
        ll ans = 0;
        for(int i = 1;i <= tot; i++)
            ans += dp[n][i]*fac[i]%mod;
        printf("Case %d: %I64d
", cas++, ans%mod);
    }
    return 0;
}