Counting Binary Trees
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 493 Accepted Submission(s): 151
Problem Description
There are 5 distinct binary trees of 3 nodes:
Let T(n) be the number of distinct non-empty binary trees of no more than n nodes, your task is to calculate T(n) mod m .

Let T(n) be the number of distinct non-empty binary trees of no more than n nodes, your task is to calculate T(n) mod m .
?
?
Input
The input contains at most 10 test cases. Each case contains two integers n and m (1 <= n <= 100,000, 1 <= m <= 10
9
) on a single line. The input ends with n = m = 0.
?
?
Output
For each test case, print T(n) mod m.
?
?
Sample Input
3 100 4 10 0 0
?
?
Sample Output
8 2
?
?
Source
?
?
Recommend
zhonglihua
乘法逆元,我們知道,卡特蘭數可以由公式,h[i]=h[i-1]*(4*i-2)/(i+1)得出,但是,我們知道,由于,是取過模的,我們如果,不還是直接除的話,是不對的,所以,我們要用乘法逆元就可以了,但是,乘法逆元,要求是互質的數, 這里,我們,把m的質因子保存下來,互素的直接算就可以了 !
#include <iostream> #include <stdio.h> #include <string.h> using namespace std; __int64 vec[40],num[40],m,index; __int64 ectgcd(__int64 a,__int64 b,__int64 & x,__int64 & y) { if(b==0){x=1;y=0;return a;} __int64 d=ectgcd(b,a%b,x,y); __int64 t=x;x=y;y=(t-a/b*y); return d; } int main() { __int64 i,j,tempm,t,k,l; __int64 n; while(scanf("%I64d%I64d",&n,&m)!=EOF&&n+m) { memset(num,0,sizeof(num)); index=0; tempm=m; for(i=2;i*i<=m;i++) { if(m%i==0) { vec[index++]=i; while(m%i==0) { m=m/i; } } } if(m!=1) vec[index++]=m; m=tempm; __int64 res=1,result=0; for(i=1;i<=n;i++) { k=4*i-2; for(j=0;j<index;j++) { if(k%vec[j]==0) { while(k%vec[j]==0) { k=k/vec[j]; num[j]++; } } } res=res*k%m; k=i+1; for(j=0;j<index;j++) { if(k%vec[j]==0) { while(k%vec[j]==0) { k=k/vec[j]; num[j]--; } } } if(k!=1) { __int64 x,y; ectgcd(k,m,x,y); x=x%m; if(x<0) x+=m; res=res*x%m; } l=res; for(j=0;j<index;j++) for(t=0;t<num[j];t++) l=l*vec[j]%m; result=(result+l)%m; } printf("%I64d\n",result); } return 0; }
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
