首页 > 代码库 > 百度之星2014初赛 - 1002 - Grids
百度之星2014初赛 - 1002 - Grids
先上题目:
Grids
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 0 Accepted Submission(s): 0
Problem Description
度度熊最近很喜欢玩游戏。这一天他在纸上画了一个2行N列的长方形格子。他想把1到2N这些数依次放进去,但是为了使格子看起来优美,他想找到使每行每列都递增的方案。不过画了很久,他发现方案数实在是太多了。度度熊想知道,有多少种放数字的方法能满足上面的条件?
Input
第一行为数据组数T(1<=T<=100000)。
然后T行,每行为一个数N(1<=N<=1000000)表示长方形的大小。
然后T行,每行为一个数N(1<=N<=1000000)表示长方形的大小。
Output
对于每组数据,输出符合题意的方案数。由于数字可能非常大,你只需要把最后的结果对1000000007取模即可。
Sample Input
2
1
3
Sample Output
Case #1: 1
Case #2: 5
Hint
对于第二组样例,共5种方案,具体方案为: 中文题意不解释,打表得出前六项为1,2,5,14,42,132是卡特兰数,所以可以使用公式:
F(n+1)=(4*n-6)*F(n)/n (n>=2)
F(1)=F(2)=1
因为需要求模,但是公式里面有除法,所以需要求逆元。同时需要注意的是问第n个数的答案不一定就是第n个卡特兰数。
上代码:
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define MAX 1000003 5 #define MOD 1000000007 6 #define LL long long 7 using namespace std; 8 9 LL s[MAX]; 10 11 LL exgcd(LL a,LL b,LL &x,LL &y){ 12 if(b==0){ 13 x=1; y=0; return a; 14 } 15 LL d = exgcd(b,a%b,x,y); 16 LL t=x;x=y;y=t-a/b*y; 17 return d; 18 } 19 20 void deal(){ 21 s[1]=s[2]=1; 22 int n = MAX; 23 LL x,y; 24 for(int i=2;i<=n;i++){ 25 s[i+1]=(4*i-6)%MOD; 26 s[i+1]=(s[i+1]*s[i])%MOD; 27 exgcd(i,MOD,x,y); 28 s[i+1]=(s[i+1]*((x+MOD)%MOD))%MOD; 29 } 30 } 31 32 int main() 33 { 34 int t,n; 35 //freopen("data.txt","r",stdin); 36 deal(); 37 scanf("%d",&t); 38 for(int z=1;z<=t;z++){ 39 scanf("%d",&n); 40 printf("Case #%d:\n",z); 41 printf("%I64d\n",s[n+2]); 42 } 43 return 0; 44 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。