首页 > 代码库 > 2017-百度之星 初赛-B
2017-百度之星 初赛-B
1001 Chess
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 177 Accepted Submission(s):
133
Problem Description
車是中国象棋中的一种棋子，它能攻击同一行或同一列中没有其他棋子阻隔的棋子。一天，小度在棋盘上摆起了许多車……他想知道，在一共N×M个点的矩形棋盘中摆最多个数的車使其互不攻击的方案数。他经过思考，得出了答案。但他仍不满足，想增加一个条件：对于任何一个車A，如果有其他一个車B在它的上方（車B行号小于車A），那么車A必须在車B的右边（車A列号大于車B）。
现在要问问你，满足要求的方案数是多少。
现在要问问你，满足要求的方案数是多少。
Input
第一行一个正整数T，表示数据组数。
对于每组数据：一行，两个正整数N和M（N<=1000，M<=1000）。
对于每组数据：一行，两个正整数N和M（N<=1000，M<=1000）。
Output
对于每组数据输出一行，代表方案数模1000000007（1e9+7）。
Sample Input
1
1 1
Sample Output
1
组合数C(max(n,m),min(n,m));
1000可以开杨辉三角。
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <cstdlib> #include <iomanip> #include <cmath> #include <cassert> #include <ctime> #include <map> #include <set> using namespace std; #define lowbit(x) (x&(-x)) #define max(x,y) (x>y?x:y) #define min(x,y) (x<y?x:y) #define MAX 100000000000000000 #define MOD 1000000007 #define pi acos(-1.0) #define ei exp(1) #define PI 3.141592653589793238462 #define ios() ios::sync_with_stdio(false) #define INF 1044266558 #define mem(a) (memset(a,0,sizeof(a))) typedef long long ll; ll dp[1001][1001]; ll n,m,t; void init() { memset(dp,0,sizeof(dp)); for(int i=1;i<=1000;i++) { dp[i][0]=dp[i][i]=1; for(int j=1;j<i;j++) { dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%MOD; } } } int main() { init(); scanf("%lld",&t); while(t--) { scanf("%lld%lld",&n,&m); if(n<m) swap(n,m); printf("%lld\n",dp[n][m]); } return 0; }
也可以费马小定理求逆元
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <cstdlib> #include <iomanip> #include <cmath> #include <cassert> #include <ctime> #include <map> #include <set> using namespace std; #define lowbit(x) (x&(-x)) #define max(x,y) (x>y?x:y) #define min(x,y) (x<y?x:y) #define MAX 100000000000000000 #define MOD 1000000007 #define pi acos(-1.0) #define ei exp(1) #define PI 3.141592653589793238462 #define ios() ios::sync_with_stdio(false) #define INF 1044266558 #define mem(a) (memset(a,0,sizeof(a))) typedef long long ll; ll dp[1001][1001]; ll n,m,t; ll quick_pow(ll x,ll y) { ll ans=1; while(y) { if(y&1) ans=ans*x%MOD; y>>=1; x=x*x%MOD; } return ans; } ll C(int n,int m) { ll ans=1; for(int i=0;i<m;i++) { ans=(ans*(n-i)%MOD)*quick_pow(i+1,MOD-2)%MOD; } return ans; } int main() { scanf("%lld",&t); while(t--) { scanf("%lld%lld",&n,&m); if(n<m) swap(n,m); printf("%lld\n",C(n,m)); } return 0; }
2017-百度之星 初赛-B
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。