bzoj1089 [SCOI2003]严格n元树(dp+高精)

1089: [SCOI2003]严格n元树

Time Limit: 1 Sec  Memory Limit: 162 MB
Submit: 1899  Solved: 954
[Submit][Status][Discuss]

Description

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

　　给出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

/*

定义S[i]代表深度<=i的严格n元树的个数

那么最后S[d]-S[d-1]就是答案

那么对于S[i]，我们由S[i-1]递推来，

我们考虑新加一个根节点，然后根节点有n个子节点，每个子节点都可以建一颗深度<=i-1的树，那么每个

子节点都有S[i-1]种选法，那么n个子节点就有S[i-1]^n选法，再加上都不选，就是深度为0的情况

那么S[i]:=（S[i-1]^n）+1；

*/

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<iomanip>

using namespace std;

struct long_int{

    int num[],cnt;

    void operator = (int y)

    {

        num[]=y;cnt=;

    }

    int& operator [] (int x)

    {

        return num[x];

    }

}S[];

void operator *= (long_int &x,long_int &y)

{

    long_int z=S[];

    int i,j;

    for(i=;i<=x.cnt;i++)

        for(j=;j<=y.cnt;j++)

        {

            z[i+j-]+=x[i]*y[j];

            z[i+j]+=z[i+j-]/;

            z[i+j-]%=;

        }

    z.cnt=x.cnt+y.cnt;

    if(!z[z.cnt])--z.cnt;

    x=z;

}

void operator ++ (long_int &x)

{

    int i=;x[]++;

    while(x[i]==)x[i]=,x[++i]++;

}

long_int operator - (long_int &x,long_int &y)

{

    long_int z=S[];

    int i;

    for(i=;i<=x.cnt;i++)

    {

        z[i]+=x[i]-y[i];

        if(z[i]<) z[i]+=,z[i+]--;

        if(z[i]) z.cnt=i;

    }

    return z;

}

long_int operator ^ (long_int x,int y)

{

    long_int z=S[];z=;

    while(y)

    {

        if(y&) z*=x;

        x*=x;y>>=;

    }

    return z;

}

ostream& operator << (ostream &os,long_int x)

{

    int i;

    os<<x[x.cnt];

    for(i=x.cnt-;i;i--)

        os<<setfill('')<<setw()<<x[i];

        //os<<x[i];

    return os;

}

int n,d;

int main()

{

    int i;

    cin>>n>>d;

    if(!d)

    {

        puts("");return ;

    }

    S[]=;

    for(i=;i<=d;i++)

        S[i]=S[i-]^n,++S[i];

    cout<<S[d]-S[d-]<<endl;

}