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元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
