2015 asia xian regional F Color (容斥 + 组合数学)

题目链接http://codeforces.com/gym/100548/attachments

Description

Input

Output

Sample Input

2

3 2 2

3 2 1

Sample Output

Case #1: 2

Case #2: 0

题意：

题解：

代码：

#include <bits/stdc++.h>

using namespace std ;

typedef long long ll ;

const ll mod = 1e9+7 ;

const int maxn = 1e6 + 10 ;

ll pow(ll a, ll n)

{

    ll ret = 1, cal = a ;

    while (n){

        if (n&1)

            ret = ret*cal%mod ;

        cal = cal*cal%mod ;

        n >>= 1;

    }

    return ret ;

}

ll inv[maxn] ;

void getinv()

{

    for (ll i = 1; i < maxn; i++)

        inv[i] = pow(i,mod-2) ;

}

ll co[maxn] ;

void comb(ll n, ll k)

{

    co[0] = 1;

    for (ll i = 1; i <= k; i++)

        co[i] = ((co[i-1] * (n-i+1)%mod) * inv[i])%mod ;

}

ll solve(ll n, ll m, ll k)

{

    comb(k,k) ;

    ll sign = 1;

    ll ans = 0;

    for (long long i = k; i >= 1; i--){

        ans = (mod + ans + ((sign*co[i]%mod)*i%mod)*pow(i-1,n-1)%mod)%mod ;

        sign = -sign ;

    }

    comb(m,k) ;

    ans = ans*co[k]%mod ;

    return ans ;

}

int main()

{

    getinv() ;

    int t;

    scanf("%d",&t) ;

    for (int _t = 1; _t <= t; _t++){

        ll n,m,k;

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

        printf("Case #%d: %lld\n",_t,solve(n,m,k)) ;

    }

    return 0 ;

}