[ICPC] 2019 南京站 B. 棋盘 | 组合计数、阅读理解

本文已参与「新人创作礼」活动， 一起开启掘金创作之路。

【ICPC】2019南京站 B. Chessboard | 组合数、阅读理解

题目链接

Problem - B - Codeforces

题目

Sunday morning has come, and all the autumn would be bright and cool, and brimming with life. There was a song in every heart, and if the heart was young the music issued at the lips. There was cheer in every face and a whoop in every step. Tom appeared on the sidewalk with a bucket of whitewash and a long-handled brush. He surveyed the stone chessboard in the park, and all gladness left him and a deep melancholy settled down upon his spirit. A giant chessboard, that is $n$ feet long and $m$ feet wide. Life to him seemed hollow, and existence but a burden.

Sighing, he dipped his brush with a little whitewash and thought how to start. He knew that he would select a starting point, which should be an arbitrary block in the chessboard. He would whitewash the block and move to an adjacent one; repeat the operation and finish his work in any place when the whole chessboard has been whitewashed. His footprints would defile a painted region even if he took off his shoes. So avoiding to go back to a completed block would be a wise choice.

But Tom's energy did not last. He began to think of the fun he had planned for this day, and his sorrows multiplied. Soon the free boys and girls would come tripping along the Yan Lake inside Nanjing University of Aeronautics and Astronautics Jiangning campus, and they would have the chance to take part in the ICPC contest facing interesting algorithms problems. Staring at the chessboard, a sudden curiosity urged him to pay attention to, between any two painted blocks, the shortest paths only passing painted blocks in which adjacent blocks should share a common edge.

"Damn it! The shortest distances may vary. I have to stop such a thing happening."

He quickly imagined a strategy that the shortest distance between any two blocks would remain unchanged after they were painted.

Now he wants to know how many different satisfactory strategies are there that can whitewash the whole chessboard. Can you help him?

题目大意

有一个 $n\times m$ 的棋盘，Tom 从任意一个格子出发，下一时刻可以到达与当前所在的格子四相邻且没有访问过的格子，他经过的格子将会被染成白色。

染色过程中，要求任意时刻两个被染过色的格子之间只经过染过色的格子的最短路径长度（四连通）不能大于它们之间的曼哈顿距离。要把整个棋盘全部染成白色，求有多少种不同的染色顺序。

思路

染色过程中，要求任意时刻两个被染过色的格子之间只经过染过色的格子的最短路径长度（四连通）不能大于它们之间的曼哈顿距离。就是说不能同一行或同一列两个染过色的格子之间存在没有染过色的格子。如下图所示：

而我们最终要染成一个矩形，假设我们已经染成了下述模样：

如果我们不立即染 A，则不论是从A的上方还是左侧再次来到 A 的旁边，都会不合题意。每当我们染出一个矩形，当前 Tom 一定在矩形的一个角上。

所以我们染整个 $n\times m$ 的矩形的路径终点一定会落在四个角上，显然他们的答案都一样。我们到过来思考，假设我们的起点是左上角，我们每次可以决定走行还是列，做出选择后一定会走到不能走才停下来。如下图所示：

如果我们选择走起点所在行，我们到达行的末尾后只能进入下一行最后一列，然后再次面临走行还是走列的选择，相当于对 $(n-1)\times m$ 的棋盘求解。因为我们每次做出选择都会相当于让整个棋盘减少一行或者减少一列，直到棋盘大小为 $1\times 1$ 为止。走行和列的次数不变，顺序可以指定，所以起点是左上角的答案就是 $C_{n+m-2}^{n-1}$。

再乘上最初 $n\times m$ 棋盘的合法重点数量即可。

代码

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
using LL=long long;
int n,m;
const int  N=2e6+5;
const LL mod=1e9+7;
LL fac[N],inv[N];
LL poww(LL a,LL b)
{
	LL ans=1;
	for (;b;b>>=1,a=a*a%mod)
		if (b&1) ans=ans*a%mod;
	return ans;
}
int main()
{
	int T;
	n=2e6;
	fac[0]=1;
	for (int i=1;i<=n;++i) fac[i]=fac[i-1]*i%mod;
	inv[n]=poww(fac[n],mod-2);
	for (int i=n;i>=1;--i) inv[i-1]=inv[i]*i%mod;
	for (scanf("%d",&T);T--;)
	{
		scanf("%d%d",&n,&m);
		n--;
		m--;
		printf("%lld\n",((n!=0)+1)*((m!=0)+1)*fac[n+m]*inv[n]%mod*inv[m]%mod);
	}
    return 0;
}