题目大意:
给你一个 m*n (0< m <1000,0< n <1000)的棋盘,问你在上面放最多的棋子的摆放方法的种数。要求:对于每一个棋子,它的上面每一行的棋子都必须在它的左边。且每一行只能有一个棋子。
分析:
其实仔细考虑,这个问题对棋盘来说是对角线对称的,所以 m n 的顺序对这道题的结果无关。所以现在我们不妨假设:
代码:
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int mod=1000000007;
int t,m,n;
LL qmod(LL x,int n)//快速幂取模
{
LL ans=1;
for(;n;n>>=1)
{
if(n&1)ans=(ans*x)%mod;
x=x*x%mod;
}
return ans;
}
LL C(int n,int m)//组合数取模
{
if(m>n)return 0;
LL ans=1;
for(int i=1;i<=m;i++)
{
ans=ans*((n-m+i)*qmod(i,mod-2)%mod)%mod;
}
return ans;
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);//n<m
int temp=0;
if(n>m)
{
temp=n;
n=m;
m=temp;
}
printf("%d\n",C(m,n)%mod);
}
}