hdu4828 Grids 百度之星初赛1002解题报告

搞ACM起步比较晚,但是对这方面兴趣很大,第一次参加百度之星,资格赛水过一道题进入初赛,结果初赛被一道题难倒了。

初赛分两场,每场筛选500人(赛程规定),而之后的结果上看,只有约250人A出题,而大多数人都是通过这道题拿到复赛入场券。这道题我一直觉得非常接近结果了,但是在最重要的环节,也就是取模上出了很大的问题,导致没有A出该题,下面是该题的分析。

题干上,大多数人可以看出看出规律,即求卡特兰数,HDOJ上有相类似的题目,但是这道题的数据量非常大,有100万之多,因而题目上要求对1000000007取模。

卡特兰数有很多递推公式,我选择的是h(n)=h(n-1)(4n-2)/(n+1);这条。

由于数据量比较大,因而我选择用打表的方式,但是这里出现了一个问题,卡特兰数的数据在不断的增大,因而一定要在取模的基础上进行递推,然而简单地进行取模会造成递推公式出错,即不能在原结果上直接取模。

比赛时就卡在这点上了,怎么想都想不出改进的方法。

直到后来做到HDOJ的拓展欧几里德的题目(HDOJ 1576),才直到这道题的解法。

除法的取模需要用extgcd的算法进行取逆,这是该题的关键。

该题代码如下:

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<iostream>
using namespace std;
__int64 h[1000001];
const int MOD=1000000007;
int extgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
int r=extgcd(b,a%b,x,y);
int t=x;
x=y;
y=t-a/b*y;
return r;
}
int main()
{
int T;
int n,i,j,x,y;
h[0]=1;
for(i=1;i<=1000000;i++)
{
h[i]=(4*i-2)%MOD;
h[i]=(h[i]*h[i-1])%MOD;
extgcd(i+1,MOD,x,y);
h[i]=(h[i]*(x+MOD)%MOD)%MOD;
}
cin>>T;
for(i=1;i<=T;i++)
{
cin>>n;
cout<<"Case #"<<i<<":"<<endl;
cout<<h[n]<<endl;
}
return 0;
}