hdu 3240

博客图片

题目链接

题目概述

给出(n)个结点,最多(n)个结点可以组成的不同形态的二叉树的数目.结果很大,所以输出的结果要对(m)取模,其中((1 leq n leq 100000), (1 leq m leq 100000000)).

一点思路

因为是最多用(n)个结点可以构成的总数,实际是1个结点,2个结点,(dots,n)个结点可以构成的不同形态的二叉树的数目之和.所以问题就转化成求(n)个相同的结点可以构成的不同的二叉树形态的数目.假设(n)个结点可以构成的二叉树的(f(n))个.对于(n)个相同的结点,首先有一个结点是根节点,然后对于剩下的(n-1)个结点来说,讲它们分成两部分,分别构成左右子树,可以分成((0,n-1),(1,n-2),dots(n-1,0))中,分别表示,左子树由(0)个结点构成右子树由((n-1))个结点构成,左子树由(1)个结点构成右子树由((n-2))个结点构成,(dots),左子树由(n-1)个结点构成右子树由(0)个结点构成,由加法原理和乘法原理:

[egin{aligned} f(n) &= f(0)f(n-1)+f(1)f(n-2)+cdots+f(n-1)f(0) \ &= sum_{i=0}^{n-1}{f(i)f(n-1-i)},qquad f(0) = 1 end{aligned} ]

这个恰好就是(Catalan)数的一个计算表示的方法.所以,(n)个相同结点可以构成的不同形态的二叉树的数目恰好是(C_n).

然后是解决计算(Catalan)数取模的问题.(C_n)的计算有三个公式:

[egin{aligned} C_n &= C_0C_{n-1}+C_1C_{n-2}+cdots+C_{n-1}C_0 = sum_{i=0}^{n-1}C_iC_{n-1-i}, qquad C_0 = 1\ C_n &= frac{4*n-2}{n+1}C_{n-1}, qquad C_0=1\ C_0 &= frac{1}{n+1}C_{2n}^n=frac{(2n)!}{(n+1)!n!} end{aligned} ]

最初我用的是第一个式子计算提交的,然后TLE.然后第二个因为有一个分式,并且不能总保证((4*n-2)\%(n+1)=0)总成立,而(C_{n-1})在前面的计算中已经取模了,很明显如果直接分子分母取模再相除结果一定是不对的,所以我最初的想法是通过通过逆元把(frac{4*n-2}{n+1}\%m)转成(((4*n-2)k)\%m)来进行计算,其中的(k)是((n+1))模(m)的逆,但是发现这个会出问题,因为((n+1)kequiv 1\, (mod m)),只有当(m)是素数的条件下才成立,比如当(n=1,m=100)时,显然是没法求出这个逆元的.然后就一直卡在这里了.┭┮﹏┭┮

进一步的想法

对于模数(m),来说,满足(m=p_1^{a_1}p_2^{a_2}cdots p_k^{a_k},\, p_i)是素数(,a_ige1.)所以可以先从((4*n-2))和((n+1))中先剔除掉(m)的素因子,如果此时的((n+1) !=1)那么可以通过求逆的方法,把原来的除法取模变成乘法逆元取模了.然后这个然后再乘上哪些提出掉的素因子再对(m)取模得到的就是(C_n\%m).

代码实现

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
// ll S[N];

// 扩展gcd
void extend_gcd(ll a, ll b, ll& x, ll& y) {
    if(b == 0){
        x = 1;
        y = 0;
        return;
    }
    extend_gcd(b, a%b, x, y);
    ll temp = x;
    x = y;
    y = temp - (a / b) * y;
}

// 计算a模m的逆
ll mod_inverse(ll a, ll m){
    ll x, y;
    extend_gcd(a, m, x,y);
    return (m + x % m) % m;
}

// // 前项和乘积类加求解,TLE
// void calculate(int n, int m){
//     memset(S, 0, sizeof(S));
//     S[0] = 1;
//     ll ans = 0;
//     for (int i = 1; i <= n; ++i){
//         for (int j = 0; j < i; ++j){
//             S[i] += S[j]*S[i-1-j];
//             S[i] %= m;
//         }
//         ans += S[i];
//         ans %= m;
//     }
//     printf("%lld
", ans);
// }

// 利用递推式和逆元取模计算
void calculate(int n, int m){
    ll primes[N] = {0};
    int cnt = 0;
    ll nums[N] = {0};
    // 计算m的素因子
    ll temp = m;
    for (ll i = 2; i * i <= temp;++i){
        if(temp% i == 0){
            primes[cnt++] = i;
            // 剔除调m中的所有素因子i
            while(temp % i == 0){
                temp /= i;
            }
        }
    }
    // 判断最后剩下m是不是一个素数
    if( temp != 1)
        primes[cnt++] = temp;
    ll pre = 1;
    ll ans = 0;
    ll cur = 1;
    for (int i = 1; i <= n; ++i){
        //去掉(4*i-2)中m的素因子,记录这些素因子的个数
        ll k = 4 * i - 2;
        for (int j = 0; j < cnt; j++){
            // (4*i-2)中包含了m的某个素因子不止一次.
            while( k % primes[j] == 0){
                ++nums[j];
                k /= primes[j];
            }
        }
        pre *= k;
        pre %= m;
        // 去掉(i+1)中m的素因子,把这些素因子的个数从前面(4*i-2)中剔除
        k = i + 1;
        for (int j = 0; j < cnt; j++){
            // (4*i-2)中包含了m的某个素因子不止一次.
            while( k % primes[j] == 0){
                --nums[j];
                k /= primes[j];
            }
        }
        // 计算剔除素因子后(i+1)的逆元
        if( k != 1)
            k = mod_inverse(k, m);
        pre *= k;
        pre %= m;
        cur = pre;
        for (int j = 0; j < cnt; j++){
            // 乘以之前剔除的素因子
            for (int k = 0; k < nums[j]; ++k)
                cur = (cur * primes[j]) % m;
        }
        ans += cur;
        ans %= m;
    }
    printf("%lld
", ans);
}

int main(int argc, const char** argv) {
    int n = 0, m = 0;
    while(scanf("%d%d", &n,&m) && (n+m != 0)) {
        calculate(n,m);
    }
    return 0;
}