CF128C Games with Rectangle

Dp或者组合数都能做。

一道Dp题全都用组合计数（虽然本人也是）。

Solution

比较显然的是，行和列独立（看了一上午没看出来）

首先考虑Dp，记$f_{i,j}$表示分了$i$次，最后一次的长度为$j$的方案数，有转移方程：
$$
f_{i,j}=\sum_{k=1}^{j-2}f_{i-1,k}\times{(j-k-1)}
$$
看着有点奇怪，但感性理解的话，后面那个就是枚举的排列，这样可以做到$O(n^3)$，可过了。

考虑组合意义，其实就是选择$2k$的互相独立的列和行（这样一定能构成唯一一种满足条件的矩阵），而行和列可选择的数量又因为边缘不能重叠，所以答案自然等于：
$$
C_{m-1}^{2k}\times C_{n-1}^{2k}
$$

Code

#include<bits/stdc++.h>
#define PII pair<int, int>
#define LL long long
using namespace std;
template <class T>
inline void read(T &res)
{
	res = 0; bool flag = 0;
	char c = getchar();
	while(c < '0' || '9' < c) {if(c == '-') flag = 1; c = getchar();}
	while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
	if(flag) res = -res; 
}
template <class T, class ...ARC>
inline void read(T &res, ARC &...com){ read(res), read(com...); }
template <class T>
void write(T res)
{
	if(res < 0) putchar('-'), res = -res;
	if(res > 9) write(res / 10);
	putchar(res % 10 + '0');
}
template <>
inline void write(char c) { putchar(c); }
template <>
inline void write(char *s) { while(*s) putchar(*s ++);}
template <class T, class ...ARC>
inline void write(T res, ARC ...com) { write(res), write(com...); } 
const int N = 1005, mod = 1e9 + 7;
int n, m, k;
int f[N][N], fac[N], inv[N];
inline void init()
{
    fac[0] = fac[1] = 1;
    for(int i = 2;i < N;i ++) fac[i] = 1ll * i * fac[i - 1] % mod;
    inv[0] = inv[1] = 1;
    for(int i = 2;i < N;i ++) inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
    for(int i = 2;i < N;i ++) inv[i] = 1ll * inv[i - 1] * inv[i] % mod;
}
inline int C(int x, int y)
{
    if(y < 0 || x < y) return 0;
    return 1ll * fac[x] * inv[y] % mod * inv[x - y] % mod;
}
int main()
{
    init();
	read(n, m, k);
    write(1ll * C(n - 1, 2 * k) * C(m - 1, 2 * k) % mod);
    return 0;
}