组合数 牛牛的棋盘
题解：
这个题目当时打比赛的时候没有写出来，还是有点难的，今天看了别人的代码，才理清思路。
其实需要注意的就是第一行第一列最后一行最后一列都必须有棋子，其他就没什么限制了，这个很容易就可以想到用组合数，就是首先求出 (n*m) 里面放 (k) 个棋子的方案数，然后减去不合法情况。
不过当时有点傻，没想清楚怎么去除不合法情况。
一共有四种不合法的情况
- 有一行或者一列没有
- 有两行或者两列或者一行一列没有
- 有三个没有
- 四个全部没有
看这个图：
-
计算第一种情况： (C((n-1)*m,k)) 或 (C(n*(m-1),k))
可以计算：
- 1、2、3、4
- 12、13、14 || 23、24、21 || 34、31、32 || 41、42、43
- 123、124、134 || 231、234、241 || 341、342、312 || 412、413、423
- 1234 || 1234 || 1234 || 1234
-
计算第二种情况，可以计算：
- 12 、23、24、14、13、34
- 123、124 || 231、234 || 241、243 || 142、143 || 132、134 || 341、342
- 1234 || 1234 || 1234 || 1234 || 1234 || 1234
-
计算第三种情况，可以计算：
- 123、124、234、134
- 1234 || 1234 || 1234 || 1234
-
计算第四种情况，可以计算：
- 1234
最后要注意一下，因为上面是四种不合法的情况，我们是要在最后答案里面减去答案的不合法情况，所以可以直接减去不合法情况，也就是偶数减去奇数，也可以求出不合法情况，然后一次性的减去，不合法情况就是奇数减去偶数。
class Solution {
public:
/**
*
* @param n int整型
* @param m int整型
* @param k int整型
* @return int整型
*/
#define ll long long
const int mod = 1e9+7;
ll c[1100][1100];
void init(int n){
memset(c, 0, sizeof(c));
for (int i = 0; i <= n; i++) {
c[i][0] = 1;
for (int j = 1; j <= i; j++)
c[i][j] = (c[i - 1][j - 1] + c[i - 1][j])%mod;
}
}
int solve(int n, int m, int k) {
// write code here
init(n*m);
ll ans=0;
for(int i=0;i<16;i++){
int x=n,y=m,cur=0;
if(i&1) cur++,y--;
if(i&2) cur++,x--;
if(i&4) cur++,y--;
if(i&8) cur++,x--;
if(cur&1) ans = (ans-c[x*y][k]+mod)%mod;
else ans=(ans+c[x*y][k])%mod;
// printf("ans=%lld i=%d cur=%d
",ans,i,cur);
}
return int(ans);
}
};
#include <bits/stdc++.h>
#define id first
#define val second
#define inf 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
using namespace std;
const int maxn=2e5+10;
const int mod =1e9+7;
typedef long long ll;
int a[maxn];
ll c[1100][1100];
void init(int n){
memset(c, 0, sizeof(c));
for (int i = 0; i <= n; i++) {
c[i][0] = 1;
for (int j = 1; j <= i; j++)
c[i][j] = (c[i - 1][j - 1] + c[i - 1][j])%mod;
}
}
int main(){
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
init(n*m);
ll ans=0;
for(int i=0;i<16;i++){
int x=n,y=m,cur=0;
if(i&1) cur++,y--;
if(i&2) cur++,x--;
if(i&4) cur++,y--;
if(i&8) cur++,x--;
if(cur&1) ans = (ans-c[x*y][k]+mod)%mod;
else ans=(ans+c[x*y][k])%mod;
// printf("ans=%lld i=%d cur=%d
",ans,i,cur);
}
printf("%lld
",ans);
}