UVA_11806

    这个题目直接计算不大好算，但是反过来去计算不符合要求的局面则容易很多。

    我们不妨设A[i]表示我们规定其中i条边上不能放，而其他的地方随便放，所得的一个结果（比如i=2，我们要枚举是哪2条边没有放，然后其他地方随便放，可以用组合数求得结果，最后将每次枚举所得的结果加起来作为A[2]的值）。再设a[i]表示有且仅有i条边上没有放的情况数（比如i=2，同样是枚举哪2条边没有放，最后C(4,2)种枚举所得的情况之和才是a[2]的值）。

   我们想要的显然是a[1]+a[2]+a[3]+a[4]，这就是所有不符合要求的情况，但是同样不好直接计算，但是A[i]却很好计算，我们只要枚举哪些边没有放，然后再用组合数计算其他地方随便放的方案数即可。我们列出通过上述规则计算所得的A[i]由哪些部分组成，比如A[1]，我们按上述规则计算之后会发现a[1]算了1次，a[2]算了2次，a[3]算了3次，a[4]算了4次，也就是A[1]=a[1]+2*a[2]+3*a[3]+4*a[4]。同样的，可以得到A[2]=a[2]+3*a[3]+6*a[4]，A[3]=a[3]+4*a[4]，A[4]=a[4]。

    这样根据上面计算所得的A[1]、A[2]、A[3]、A[4]可以得到a[1]+a[2]+a[3]+a[4]=A[1]-A[2]+A[3]-A[4]，这样就能得到我们所要的结果了。

#include
     
      #include
      
       #define MOD 1000007int M, N, K, C[410][410];void prep(){    memset(C, 0, sizeof(C));    C[0][0] = 1;    for(int i = 1; i <= 400; i ++)    {        C[i][0] = 1;        for(int j = 1; j <= i; j ++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;    }}void solve(){    int ans, A[5] = {
   0};    for(int i = 1; i < 16; i ++)    {        int cnt = 0, t = 0, n = N, m = M;        for(int j = 0; j < 4; j ++)            if(i & 1 << j)            {                ++ cnt;                if(j < 2) -- n;                else -- m;            }        if(K <= n * m)        {            t = C[n * m][K];            A[cnt] = (A[cnt] + t) % MOD;        }    }    ans = A[1] - A[2] + A[3] - A[4];    printf("%d\n", ((C[N * M][K] - ans) % MOD + MOD) % MOD);}int main(){    prep();    int t;    scanf("%d", &t);    for(int tt = 1; tt <= t; tt ++)    {        scanf("%d%d%d", &M, &N, &K);        printf("Case %d: ", tt);        if(K > N * M) printf("0\n");        else solve();    }    return 0;}