题目大意是：
在一个m行n列的矩形网格中放置k个相同的石子，问有多少种方法？每个格子最多放一个石子，所有石子都要用完，并且第一行、最后一行、第一列、最后一列都要有石子。
容斥原理。如果只是n * m放石子,那么最后的结果，就是C(n*m,k).我们设A为第一行不放石头的总数,B为最后一行不放石子的总数,C为第一列不放石子的总数,D为最后一列不放石子的总数.则问题转化为在全集S中,求不在A,B,C,D部分的解.则答案为S - | A | - | B |- | C | - | D | + | A ^ B|......用一个二进制枚举状态,统计就可以了。
// Asimple
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <vector>
#include <string>
#include <cstring>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#define INF 0x3f3f3f3f
#define mod 1000007
#define debug(a) cout<<#a<<" = "<<a<<endl
#define test() cout<<"============"<<endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = +;
ll n, m, T, len, cnt, num, ans, Max, k;
ll a[maxn][maxn];void input(){
memset(a, , sizeof(a));
a[][] = ;
for(int i=; i<maxn; i++) {
a[i][] = a[i][i] = ;
for(int j=; j<=i; j++) {
a[i][j] = (a[i-][j] + a[i-][j-])%mod;
}
} int cas = ;
cin >> T;
while( T-- ) {
cin >> n >> m >> k;
ans = ;
for(int s=; s<; s++) {
cnt = ;
int r = n, c = m;
if( s& ) { cnt++; r--; }
if( s& ) { cnt++; r--; }
if( s& ) { cnt++; c--; }
if( s& ) { cnt++; c--; }
if( cnt& ) ans = ( ans+mod - a[r*c][k])%mod;
else ans = ( ans + a[r*c][k])%mod;
}
cout << "Case " << cas ++ << ": ";
cout << ans << endl;
}
} int main() {
input();
return ;
}