亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

hdu3240 Counting Binary Trees

系統 1723 0

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 .
?

?

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;

}


    


?

hdu3240 Counting Binary Trees


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

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

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 二区三区 | 成年人一级黄色片 | 乱码一区二区三区完整视频 | 狠狠色婷婷丁香综合久久韩国 | 99久久免费看精品国产一区 | 日日操天天| 99国产福利视频在线观看 | 91精品国产露脸在线 | 视频一区国产 | 关婷哪一级毛片高清免费看 | 伊人久久精品亚洲精品一区 | 亚洲麻豆| 国产乱码亚洲精品一区二区 | 可以免费观看的毛片 | 久久青草91线频免费观看 | 永久黄网站色视频免费观看 | 久久国内精品自在自线观看 | 四虎成年永久免费网站 | 日韩我不卡 | 欧美成人午夜做爰视频在线观看 | 四虎影院永久在线观看 | 四虎一影院区永久精品 | 国产无套乱子伦精彩是白视频 | 亚洲国产成人久久笫一页 | 欧美精品国产一区二区 | 亚洲精品国产啊女成拍色拍 | 国产草草视频 | 九色国产在视频线精品视频 | 国产成人久久精品二区三区 | 亚洲精品美女在线观看 | 免费在线观看黄色的网站 | 国产三级做爰在线观看∵ | 一区二区三区四区在线观看视频 | 国产精品视频福利视频网 | 亚洲精品综合久久中文字幕 | 日韩欧美精品有码在线观看 | 四虎影视永久地址www成人污 | 欧美精品99久久久久久人 | 日韩第一页在线 | 久久久亚洲欧美综合 | 国产精品线在线精品国语 |