HDU3240 Counting Binary Trees （卡特兰数，拓欧求逆元）

ゞ浴缸里的玫瑰 2022-06-11 01:06 97阅读 0赞

##                           Counting Binary Trees  [HDU - 324][][0][HDU - 324]       There are 5 distinct binary trees of 3 nodes:    ![0b1e0fa4d5802f5ea0d5546f4947f7d6_v_1500604454][]   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       这道题的题意就是说给你一个n，问所有结点数不大于n的二叉树一共有多少种，结果模m。  想做这道题首先我们要知道一个概念，Catalan数——卡特兰数。  卡特兰数又称卡塔兰数，英文名Catalan number，是组合数学中一个常出现在各种计数问题中出现的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)的名字来命名，其前几项为 : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ...     卡特兰数有四种递推关系：  h(0)=1,h(1)=1;  递推式\[1\] ：h(n)= h(0)\*h(n-1)+h(1)\*h(n-2) + ... + h(n-1)h(0) (n>=2)   递推式\[2\]  ：h(n)=h(n-1)\*(4\*n-2)/(n+1);   递推式\[3\] ：h(n)=C(2n,n)/(n+1) (n=0,1,2,...)   递推式\[4\] ：h(n)=c(2n,n)-c(2n,n+1)(n=0,1,2,...)     卡特兰数的典型应用：  1，括号化   矩阵连乘： P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？(h(n)种)  2，出栈次序   一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列?  3，凸多边形三角划分   在一个凸多边形中，通过若干条互不相交的对角线，把这个多边形划分成了若干个三角形。任务是键盘上输入凸多边形的边数n，求不同划分的方案数f（n）。比如当n=6时，f（6）=14。  4，给定节点组成二叉搜索树   给定N个节点，能构成多少种不同的二叉搜索树？   （能构成h（N）个）  5，n对括号正确匹配数目   给定n对括号，求括号正确配对的字符串数，例如：   0对括号：\[空序列\] 1种可能   1对括号：() 1种可能   2对括号：()() (()) 2种可能   3对括号：((())) ()(()) ()()() (())() (()()) 5种可能   那么问题来了，n对括号有多少种正确配对的可能呢？       以上这些问题都要用到卡特兰数，所以我们这道题自然就可以得知，这是一道前n个卡特兰数相加模m的问题。  这道题我们用递推式\[2\]  ：h(n)=h(n-1)\*(4\*n-2)/(n+1);，乘法求模没有问题，但是除法求模就需要用到逆元了。除数有逆元的充要条件是 gcd(a,mod)==1，也就是除数与要模的那个数互质。所以在这里我们要先把4\*n-2质因数分解，（注意！此处的质因数分解分解出来的素数必须满足m%prime==0）分解出来的素数存在一个数组里并++，一直分解到它与m的因子全部互质，然后就可以直接把剩下的乘上，再把n+1也质因数分解，（这里和上面一样！）分解出来的素数如果在之前的数组里存在就--，一直分解到它与m的因子全部互质我们就可以用拓展欧几里得来求逆元，拓欧求逆元的模板如下  `LL exgcd(LL a, LL b, LL &x, LL &y)//拓展欧几里得 { if (b == 0) { x = 1; y = 0; return a; } LL ans = exgcd(b, a%b, x, y); LL TT = x; x = y; y = TT - a / b*y; return ans;//ans是a，b的最大公约数 } //计算模n下a的逆，不存在返回 -1 LL inv(LL a, LL n) { LL x, y; return exgcd(a, n, x, y) == 1 ? (x + n) % n : -1; }`  求出逆元之后我们也就可以直接乘上了。最后我们再把素数数组里残余的素数全部也乘上，当前这一步的卡特兰数就求完了，然后只需要循环指定次数就是答案了。AC代码如下。  `#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <cstdlib> #include <cmath> #include <vector> #include <queue> #include <map> #include <algorithm> #include <set> #include <functional> using namespace std; typedef long long LL; typedef unsigned long long ULL; const int INF = 1e9 + 5; const int MAXN = 100005; const int MOD = 1000000007; const double eps = 1e-8; const double PI = acos(-1.0); int NN, MM; int t; int num[MAXN]; int prime[MAXN], primesize; LL exgcd(LL a, LL b, LL &x, LL &y)//拓展欧几里得 { if (b == 0) { x = 1; y = 0; return a; } LL ans = exgcd(b, a%b, x, y); LL TT = x; x = y; y = TT - a / b*y; return ans;//ans是a，b的最大公约数 } //计算模n下a的逆，不存在返回 -1 LL inv(LL a, LL n) { LL x, y; return exgcd(a, n, x, y) == 1 ? (x + n) % n : -1; } void solve1(LL &ans, LL x)//处理4*n-2 { int i; for (i = 1; i <= primesize; i++) { while (x%prime[i] == 0) { x /= prime[i]; num[i]++; } } ans = (ans*x) % MM; } void solve2(LL &ans, LL x)//处理n+1 { int i; for (int i = 1; i <= primesize; i++) { while (x%prime[i] == 0 && num[i]>0) { num[i]--; x /= prime[i]; } } if (x > 1) { ans = (ans*inv(x, MM)) % MM; } } LL work() { LL ANS = 1; LL RES; LL sol = 1; for (int i = 2; i <= NN; i++) { solve1(ANS, 4 * i - 2); solve2(ANS, i + 1); RES = ANS; for (int j = 1; j <= primesize; j++) { for (int k = 0; k < num[j]; k++) { RES = (RES*prime[j]) % MM; } } sol = (sol + RES) % MM; } return sol; } int main() { while (scanf("%d%d", &NN, &MM) != EOF) { memset(num, 0, sizeof(num)); if (NN == 0 && MM == 0) break; primesize = 0; t = MM; for (int i = 2; i*i <= t; i++) if (t%i == 0) { prime[++primesize] = i; while (t%i == 0) t /= i; } if (t>1) prime[++primesize] = t; printf("%lld\n", work()); } }`            ##

[HDU - 324]: https://vjudge.net/problem/13374/origin
[0b1e0fa4d5802f5ea0d5546f4947f7d6_v_1500604454]: https://odzkskevi.qnssl.com/0b1e0fa4d5802f5ea0d5546f4947f7d6?v=1500604454