首页 > 代码库 > 百度之星2014初赛 - 1002 - Grids

百度之星2014初赛 - 1002 - Grids

2024-07-05 23:23:54   227人阅读

先上题目：

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)表示长方形的大小。
 

 

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 }
1002

 


联系
我们