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