Andrew Stankevich's Contest (21) J dp+组合数

坑爹的，，组合数模板，，，

6132

njczy2010

1412

Accepted

5572 MS

50620 KB

C++

1844 B

2014-10-02 21:41:15

J - 2-3 Trees

Time Limit: 12000/6000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Submit Status

Problem Description

2-3 tree is an elegant data structure invented by John Hopcroft. It is designed to implement the same functionality as the binary search tree. 2-3 tree is an ordered rooted tree with the following properties:

the root and each internal vertex have either 2 or 3 children;
the distance from the root to any leaf of the tree is the same.

The only exception is the tree that contains exactly one vertex — in this case the root of the tree is the only vertex, and it is simultaneously a leaf, i.e. has no children. The main idea of the described properties is that the tree with l leaves has the height O(log l). Given the number of leaves l there can be several valid 2-3 trees that have l leaves. For example, the picture below shows the two possible 2-3 trees with exactly 6 leaves.

Given l find the number of different 2-3 trees that have l leaves. Since this number can be quite large, output it modulo r.

Input

Input file contains two integer numbers: l and r (1 ≤ l ≤ 5 000, 1 ≤ r ≤ 10⁹).

Output

Output one number — the number of different 2-3 trees with exactly l leaves modulo r.

Sample Input

6 1000000000

7 1000000000

Sample Output

2

3

题解转自：http://acdream.info/topic?tid=3623

J题：问你一棵有l个叶子的2-3叉树有多少种拓扑结构，结果对r取余。。。 2-3叉树的定义为所有非叶子节点要么有2个儿子，要么有3个儿子，并且所有叶子到根的距离相等。。。（关于那个O(logn)。。。其实这句话完全是废话，貌似好多人被这句废话给坑到了。。大O只是一个标记，表示渐进的意思，就是说这种树的高度和叶子数n成渐进对数关系）

J题：首先预处理出前2500行的组合数（杨辉三角递推即可，别忘了取余），然后初始化dp[1]=1，若只有根，也有一种情况
然后进行dp，注意到一个性质，2-3树的所有叶子都在同一层，于是就可以通过排列组合来计算叶子的方法数。
于是就转移到了上一层的情况，一层一层记忆化上去，或者递推下来= =。。反正是单组数据~~~

注意用 lld。。。

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #include<map>

 #include<string>

 //#include<pair>

 #define N  5005

 #define M 15

 #define mod 10000007

 //#define p 10000007

 #define mod2 100000000

 #define ll long long

 #define LL long long

 #define maxi(a,b) (a)>(b)? (a) : (b)

 #define mini(a,b) (a)<(b)? (a) : (b)

 using namespace std;

 ll l,r;

 ll dp[N];

 ll C[N/][N/];

 void ini()

 {

    // memset(C,0,sizeof(C));

     int i,j;

     for(i=; i<=l/; ++i)

     {

         C[i][] = ;

         C[i][i] = ;

         for(j=; j<=l/; ++j){

             C[i][j] = (C[i-][j] + C[i-][j-]) % r;

         }

     }

 }

 void solve()

 {

     ll i;

     ll num;

     ll st;

     memset(dp,,sizeof(dp));

     dp[]=;

     dp[]=;

     dp[]=dp[]=;

     for(i=;i<=l;i++){

         st=;

         if(i%==){

             st=;

         }

         for(;*st<=i;st+=){

             num=st+(i-*st)/;

            dp[i]=(dp[i]+(C[num][st]*dp[num])%r)%r;

         }

     }

 }

 void out()

 {

     //for(int i=1;i<=l;i++) printf(" i=%d dp=%d\n",i,dp[i]);

     printf("%lld\n",dp[l]);

 }

 int main()

 {

    // freopen("data.in","r",stdin);

     //freopen("data.out","w",stdout);

     //scanf("%d",&T);

    // for(int ccnt=1;ccnt<=T;ccnt++)

    // while(T--)

     while(scanf("%lld%lld",&l,&r)!=EOF)

     {

         //if(n==0 && m==0 ) break;

         //printf("Case %d: ",ccnt);

         ini();

         solve();

         out();

     }

     return ;

 }

巴特西