JOI2013春合宿Day2 マスコットの片付け (Mascots)

問題

http://www.ioi-jp.org/camp/2013/2013-sp-tasks/2013-sp-day2.pdf]
マスコットを縦*横の長方形の領域が埋まるように置いていく。
ただし、個のマスコットは既に置かれている。(位置は与えられる)
置いていく途中でマスコットの集合が長方形になったら幸せなので、そのようにしたい。
置いていく途中でマスコットの集合が最多回長方形になるようなマスコットの置き方は何通りあるか。

解法

まず最多回長方形が作れる置き方を考えます。
最初はすべてのマスコットを含む最小の長方形を作ります。
この通り数は単純に順列で求まります。
その長方形から4方向に長方形を1だけ拡張する置きかたを繰り返していけば、必ず最多回長方形ができます。
4方向に長方形を1だけ拡張するとき、マスコットの置き方は

そこで、

というDPを考えます。でもこれは最悪計算量がだから、明らかに間に合いません。

ここで、上に拡張するときと下に拡張するとき、右に拡張するときと左に拡張するときはそれぞれ拡張する方向に対しての幅がどんなときも同じであることを利用して、まとめて計算できないか考えます。
和の法則で

とします。
例を考えてみましょう。

R = 3, C = 3
○○○
○×○
○×○
(×はマスコット)

拡張の仕方を矢印を使って表すと、
各拡張の仕方とそれに対してのマスコットの置き方の通り数は、
(拡張の仕方) : 通り数

さっきの考察から、上に拡張しようが下に拡張しようが(同様に右と左も)右側の順列には関係ありません。
そこで縦に拡張するのを|、横に拡張するのを-として表すと

例えば|--だと↑→←、↑←→の2つの拡張の仕方が含まれていますが、これは組み合わせを使って計算で出せます。
= 上に拡張できる回数、 = 下に拡張できる回数、 = 右に拡張できる回数、 = 左に拡張できる回数　とおくと、

組み合わせはパスカルの三角形を利用して前計算しておけばよいです。

あとはDPを使って右側の順列部分も前計算しておきます。

漸化式は

すると答えは

計算量は最初の順列計算がパスカルの三角形の前計算が、DPが(事前の階乗計算が必要)なので、全体としてもです。

コード

using namespace std;
 
typedef long long ll;
 
#define int long long
 
const int MOD = 1e9 + 7;
 
int R, C, N;
int dp[3002][3002], memo[3001], combination[3001][3001];
 
int Factorial(int n)
{
	if (n > 3000) return Factorial(n - 1) * n % MOD;
	if (memo[n] != 0) return memo[n];
	return memo[n] = Factorial(n - 1) * n % MOD;
}
 
signed main()
{
	memo[0] = 1;
	combination[0][0] = 1;
 
	pair<int, int> sr(LLONG_MAX / 2, 0), sc(LLONG_MAX / 2, 0);
	cin >> R >> C >> N;
	for (int i = 0; i < N; i++)
	{
		int a, b;
		cin >> a >> b;
		sr.first = min(sr.first, a);
		sr.second = max(sr.second, a);
		sc.first = min(sc.first, b);
		sc.second = max(sc.second, b);
	}
	int ans = Factorial((sr.second - sr.first + 1) * (sc.second - sc.first + 1) - N);
	
	for (int i = 0; i < max(R, C); i++)
	{
		for (int j = 0; j <= i; j++)
		{
			combination[i + 1][j] = (combination[i + 1][j] + combination[i][j]) % MOD;
			combination[i + 1][j + 1] = (combination[i + 1][j + 1] + combination[i][j]) % MOD;
		}
	}
 
	dp[sr.second - sr.first + 1][sc.second - sc.first + 1] = 1;
	for (int i = sr.second - sr.first + 1; i <= R; i++)
	{
		for (int j = sc.second - sc.first + 1; j <= C; j++)
		{
			if (dp[i][j] > 0) continue;
			dp[i][j] = dp[i - 1][j] * Factorial(j) + dp[i][j - 1] * Factorial(i);
			dp[i][j] %= MOD;
		}
	}
	int nr = R - (sr.second - sr.first + 1), kr = sr.first - 1;
	int nc = C - (sc.second - sc.first + 1), kc = sc.first - 1;
	ans = ans * dp[R][C] % MOD;
	ans = ans * combination[nr][kr] % MOD;
	ans = ans * combination[nc][kc] % MOD;
	printf("%lld\n", ans);
	return 0;
}