题意：给定一个n*m的有格子的矩形，现在又两个人在矩形内轮流画矩形，每次都必须沿着格子的轮廓来画，新画的矩形必须嵌套在上一个矩形里面，并且不能和上一个矩形有任何的重复的点。现在这两个人一共会画k次，问一共有多少种不同的画法。
这是一个相当好的排列组合题。当然也可以用DP来解。
解决本题最最最关键的是要认识到，n和m两个维度是相互独立的，它们互不干扰。
这样，可以先来解决线段嵌套的问题，假设我们现在又一根长为M的线段，每1米有一个标记点，现在给你K次机会，不断的从当前的线段的中部去截取一部分，每次截取的时候必须以标记点为端点，问你一共有多少种方法。这显然是C(M-1,2*K)种。为什么呢？因为这相当于从线段的M-1个标记点上(两端不算)上任选2*K个点，比如说要截取2次，那肯定选了4个点，从左至右分别是a1,a2,a3,a4,那么自然就形成了第一次截取的是a1a4,第二次截取的是a2a3，所以答案就是C(M-1,2*K)种。
现在问题变成了二维的了，那么答案还是很简单，就是C(m-1,2*k)*C(n-1,2*k)
有的时候，如果能从题目中提取出独立的子问题，那么题目就非常容易解决了。
1 #include <stdio.h> 2 typedef long long LL; 3 const int MOD = 1000000007; 4 LL C[1<<10][1<<11]; 5 6 void init(){ 7 C[0][0] = 1; 8 for(int i = 0;i < (1<<10);i++){ 9 C[i][0] = C[i][i] = 1; 10 for(int j = 1;j < i;j++) 11 C[i][j] = (C[i-1][j] + C[i-1][j-1]) % MOD; 12 } 13 } 14 15 int main(){ 16 init(); 17 int n,m,k; 18 scanf("%d%d%d",&n,&m,&k); 19 printf("%lld\n",(C[n-1][2*k] * C[m-1][2*k]) % MOD); 20 return 0; 21 }