hdu 6114 chess（排列组合）

时间：2023-03-10 02:15:16
hdu 6114 chess（排列组合）

Chess

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 299    Accepted Submission(s): 206

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

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

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

对于每组数据：一行，两个正整数N和M（N<=1000，M<=1000）。

Output
对于每组数据输出一行，代表方案数模1000000007（1e9+7）。
Sample Input
1
1 1 
Sample Output
1
Source
Recommend
liuyiding   |   We have carefully selected several similar problems for you:  6119 6118 6117 6116 6115 
比赛当时想了半天，模拟了半天，诶，太弱了
就是求C(n，m)
用普通的求C(n，m）或是lucas都可以
#include <iostream>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<map>

#include<vector>

#include<cmath>

#include<cstring>

//#include<bits/stdc++.h>

using namespace std;

long long C[][];

#define LL long long

int t,n,m;

const long long p=1e9+;

void pre()  //i表示n，j表示m

{

    C[][]=C[][]=;

    for(int i=;i<=;i++)

    {

        C[i][]=;

        for(int j=;j<=;j++)

          C[i][j]=(C[i-][j]+C[i-][j-])%mod;

    }

    return;

}

int main()

{

   pre();

   scanf("%d",&t);

   while(t--)

   {

       scanf("%d%d",&n,&m);

       if (n<m) swap(n,m);

       printf("%lld\n",C[n][m]);

   }

   return ;

}

相关文章