题目链接

https://nanti.jisuanke.com/t/42396

参考

参考题解

洛谷日报 乘法逆元

思路

神仙思维题。

原本的暴力想法是,把n*m矩形当中选一个起点进行扩展判断是否合法(用这想法打表代码都难写);
题解思路是,从一个1*1的矩阵扩展行和列变成n*m的矩形,计算组合数。

本题要找到一个很巧妙的特点:如果当前被染色的区域是个矩形,那么最后一个被染色的点,一定在角上。

最开始是1*1的矩形,也可以认为它是一个角,每次把它进行扩展一层,则行数+1 或者 列数+1,直到变成n*m的矩形。行扩充n-1次,列扩充m-1次,总共扩充n+m-2次,扩充方案显然为$C(n+m-2,n-1)$种。

在$C(n+m-2,n-1)$种方案中任选一个,也就是说如果固定行列扩充顺序,每次扩展得到矩形的终点都是4个(4个角),直到最后得到的矩形的终点也是有4个(这个规律可以画图看看)。即对于一个确定行列扩充顺序的方案,可以有4种结果,所以答案还要乘4。

$$ans=4*C(n+m-2,n-1)\%mod$$

对于求组合数取模,可以推出:$C(n,m)\%mod=\frac {n!}{m!(n-m)!}\%mod=n!(m!)^{-1}*[(n-m)!]^{-1}\%mod$
其中$(m!)^{-1}$表示$m!$模$mod$意义下的逆元,代码中用inv[m]表示。

模数mod=1e9+7为质数可以保证在[1,mod-1]中逆元均存在:
在这里插入图片描述
所以可以放心的递推求阶乘及其逆元,然后求组合数即可。另外注意特判n=1和m=1。

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e6,mod=1e9+7;
ll n,m,fac[N+10],inv[N+10];
// fac[i]是(i!)%mod
// inv[i]是inv(i!),也就是i!的模mod逆,即逆元
ll qpow(ll a,ll b)
{
    ll s=1;
    while(b)
    {
        if(b&1)s=s*a%mod;
        a=a*a%mod;
        b/=2;
    }
    return s%mod;
}
void init()
{
    fac[0]=1;
    for(ll i=1;i<=N;i++)
        fac[i]=fac[i-1]*i%mod;
    // 费马小定理,若mod为素数且a与mod互素,则有a^(mod-1)%mod=1%mod
    // ax%mod=1%mod 其中x为逆元,则x=a^(mod-2)
    inv[N]=qpow(fac[N],mod-2); // (N!)^(mod-2)
    // (i+1)/[(i+1)!]%mod = 1/(i!)%mod
    // (i+1)*inv[i+1]%mod = inv[i]%mod
    for(ll i=N-1;i>=1;i--)
        inv[i]=(i+1)*inv[i+1]%mod; 
}
int main()
{
    ios::sync_with_stdio(false);
    init();
    int T;cin>>T;
    while(T--)
    {
        cin>>n>>m;
        if(n==1||m==1)printf("2\n");
        else printf("%lld\n",4*fac[n+m-2]*inv[n-1]%mod*inv[m-1]%mod);
    }
    return 0;
}