hdu5673 Robot 卡特蘭數默慈金數 -开发者知识库

hdu5673 Robot 卡特蘭數默慈金數 -开发者知识库,第1张

題目鏈接:http://acm.hdu.edu.cn/showproblem.php?pid=5673

分析:

  這道題是一道裸的默慈金數,比較容易想到的是用卡特蘭數來做。不了解的可以先學習一下。

  卡特蘭數http://www.cnblogs.com/yaoyueduzhen/p/5456490.html

  默慈金數http://www.cnblogs.com/yaoyueduzhen/p/5456530.html

  記路徑長度為nn,那么機器人最多向右走n/2​​⌋步並向左走n/2​​⌋步。

      Ans(n)=C​(n,2i)​​ Catalan(i

  其中 C(n,2i) 表示從n個物品中取2*i個的組合數,Catalan(n)表示第n個卡特蘭數,0 <= i <= ⌊n/2​​

  基於n的取值范圍,此題可以預處理出1,000,001以內的乘法逆元、卡特蘭數。

  每次詢問,都可以遞推組合數,或者提前一次性預處理好階乘和階乘的逆元得到組合數;累加組合數與相應卡特蘭數的乘積,得到答案。

  事實上,Ans(n)是第n個默慈金數,利用遞推公式可以快速求出。

 

卡特蘭數代碼:

 1 #include<iostream>
2 #include<cstdio>
3 #include<cmath>
4 #include<cstring>
5
6 using namespace std;
7 const long long mod=1000000007;
8 long long n;
9 long long ans[1100000],ni[1100000];
10
11 long long power(long long a,long long n,long long m)
12 {
13 long long ans=1,tmp=a;
14 while(n)
15 {
16 if(n&1)
17 ans=ans*tmp%m;
18 tmp=tmp*tmp%m;
19 n=n>>1;
20 }
21 return ans%m;
22 }
23
24 void init()
25 {
26 ans[0]=1;
27 ans[1]=1;
28 for(long long i=1;i<=1000005;i )
29 ni[i]=power(i,mod-2,mod)%mod;
30 for(long long i=2;i<=1000000;i )
31 ans[i]=(4*i-2)%mod*ans[i-1]%mod*ni[i 1]%mod;
32 }
33
34 int main()
35 {
36 init();
37 int T;
38 scanf("%d",&T);
39 while(T--)
40 {
41 scanf("%lld",&n);
42 long long res=0,tmp=1;
43 for(long long i=0;i*2<=n;i )
44 {
45 res=(res tmp*ans[i]%mod)%mod;
46 tmp=tmp*(n-2*i)%mod*(n-2*i-1)%mod*ni[2*i 1]%mod*ni[2*i 2]%mod;
47 }
48 cout<<res<<endl;
49 }
50 return 0;
51 }

最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复