BZOJ 1089: [SCOI2003]严格 n 元树

如果一棵树的所有非叶节点都恰好有 n 个儿子，那么我们称它为严格 n 元树。如果该树中最底层的节点深度为 d （根的深度为 0），那么我们称它为一棵深度为 d 的严格 n 元树。例如，深度为 2 的严格 2 元树有三个，如下图：

给出 n, d，编程数出深度为 d 的 n 元树数目。

Input

仅包含两个整数 n, d(0 < n <= 32, 0 <= d <= 16)

Output

仅包含一个数，即深度为 d 的 n 元树的数目。

Sample Input

【样例输入 1】
2 2

【样例输入 2】
2 3

【样例输入 3】
3 5

Sample Output

【样例输出 1】
3

【样例输出 2】
21

【样例输出 2】
58871587162270592645034001

Solution

我们用 $f(d)$ 表示深度不大于 $d$ 的 $n$ 元树数目，则答案为 $f(d)-f(d-1)$。
当深度为 $d$ 时，可以看做一棵深度为 $1$ 的 $n$ 元树，每个叶子节点向下都有 $d(n-1)$ 种可能，再加上深度为 $0$ 的情况，可得出 $f(d)=f(d-1)^n+1$。

Code

#include<cstdio>
#include<memory.h>
#include<cstring>

#define maxnum 100
#define cas 1000000000

int a[maxnum],b[maxnum],t[maxnum],al=1,bl;

inline void mul()
{
    memset(t,0,(al+bl+1)*4);
    for(int i=0;i<al;i++)
        for(int j=0;j<bl;j++)
        {
            long long f=(long long)a[i]*b[j];
            t[i+j]+=f%cas;
            if(t[i+j]>=cas)t[i+j]-=cas,t[i+j+1]++;
            t[i+j+1]+=f/cas;
            if(t[i+j+1]>=cas)t[i+j+1]-=cas,t[i+j+2]++;
        }
    if(t[al+bl-1])al=al+bl;else al=al+bl-1;
    memcpy(a,t,al*4);
}

inline void print(int *a)
{
    printf("%d",a[al-1]);for(int i=al-2;i>=0;i--)printf("%09d",a[i]);printf("\n");
}

int main()
{
    int n,d;
    scanf("%d%d",&n,&d);
    a[0]=1;
    while(d--)
    {
        memcpy(b,a,al*4);
        bl=al;
        for(int i=1;i<n;i++)mul();
        a[0]++;
        for(int i=0;a[i]>=cas;i++)a[i]-=cas,a[i+1]++;
        if(a[al])al++;
    }
    for(int i=0;i<bl;i++)a[i]-=b[i];
    for(int i=0;i<al;i++)if(a[i]<0)a[i]+=cas,a[i+1]--;
    if(!a[al-1])al--;
    print(a);
    printf("\n");
    return 0;
}

日期： 2016-09-08

标签： BZOJ 高精度 找规律

这是一篇旧文，原始文章及评论可在 https://oldblog.mcfx.us/archives/17/ 查看。