Des丨tiny丶柠凉

蓦然回首,前尘不堪流连,自卿离去,暗淡了这俗世繁华,只余孤影几度徘徊,独酌月下,对影成殇;

时间留不住记忆的海,不过是黯然神伤,默默着无奈。


Chess

传送门

题目描述

車是中国象棋中的一种棋子,它能攻击同一行或同一列中没有其他棋子阻隔的棋子。一天,小度在棋盘上摆起了许多車……他想知道,在一共N×M个点的矩形棋盘中摆最多个数的車使其互不攻击的方案数。他经过思考,得出了答案。但他仍不满足,想增加一个条件:对于任何一个車A,如果有其他一个車B在它的上方(車B行号小于車A),那么車A必须在車B的右边(車A列号大于車B)。

现在要问问你,满足要求的方案数是多少。


Input

第一行一个正整数T,表示数据组数。

对于每组数据:一行,两个正整数N和M(N<=1000,M<=1000)。


Output

对于每组数据输出一行,代表方案数模1000000007(1e9+7)。


解题思路

手推了下发现就是对应在一串n个方格上取m个车放(n>m),然后看下横着放和竖着放都一样的。所以就是C(n,m)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<deque>
#include<queue>
#include<stack>
#include<vector>
#define LL long long
#define MAX -999999999
#define MIN 999999999
using namespace std;
int a[1005],p = 1e9+7;
LL f[1000005],inv[1000005];
LL fast_pow(LL x,int n){
LL ans = 1;
while (n > 0) {
if (n & 1)
ans = (LL)(ans * x)%p;
x = (LL)(x * x)%p;
n >>= 1;
}
return ans % p;
}
LL CC(int n,int m){
if(m < 0 || m > n)
return 0;
LL re = 1;
for(int i = 0;i < m;i++){
re = re * (n - i)%p * fast_pow(i+1,p-2)%p;
}
return re%p;
}
int main(){
int n,m,T;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
if(n < m) n^=m,m^=n,n^=m;
printf("%d\n",CC(n,m));
}

return 0;
}

Markdown

最近的文章

【UER#2】手机的生产

传送门题目链接 由于电信技术的发展,人人都可以通过手机互相联系。 有一位电信大佬最近想生产一大批手机,然而从生产线上一台一台地生产实在太慢了,于是他想出了一个办法 —— 让手机自我复制。 于是他给手机加上了一个内置的函数 fork()。手机的程序如果调用这个函数,那么手机会生产出一台完全一模一样的手 …

于 继续阅读
更早的文章

[UOJ Round #8]赴京赶考

传送门题目描述 高中,高中,短暂的三年。NOI是高中结业考试,而高考在每年暑假举行。 高二暑假,这是你最后一次参加高考的机会。你已经为了高考停课很久了,OI的知识很久没管了。你并没有能力用一年时间补起别人三年的OI课程。这是你的最后一战,如果你失败了,可能就不能工地搬砖只能去清华了。 这天你背上行囊 …

于  贪心 继续阅读