【bzoj 十连测】[noip2016十连测第八场]Problem C: 幻魔皇（递推）

Problem C: [noip2016十连测第八场]幻魔皇

Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 16 Solved: 10
[ Submit][ Status][ Web Board]

Description

http://www.lydsy.com/JudgeOnline/upload/201610/test8888.rar

幻魔皇拉比艾尔很喜欢斐波那契树，他想找到神奇的节点对。所谓斐波那契树，根是一个白色节点，每个白色节点都有一个黑色节点儿子，而每个黑色节点则有一个白色和一个黑色节点儿子。神奇的节点对则是指白色节点对。请问对于深度为n的斐波那契树，其中距离为i的神奇节点对有多少个？拉比艾尔需要你对于1<=i<=2n的所有i都求出答案。

Input

一行一个正整数n,n<=5000

Output

一行2n个整数表示答案，对123456789取模。

Sample Input

Sample Output

0 2 3 3 1 1 0 0 0 0

HINT

【题解】【递推+乱搞】
【首先，由于这是斐波那契树，所以，白点和黑点每一层的数量之间，分别满足斐波那契数列。】
【这样，我们就可以预处理每一层的白点数f[i]、前n层的白点数sum[i]】
【分两种情况讨论：1）一个点对中，一个点是这两个点的lca；2）黑点是这个点对的lca】
【1）枚举两点之间的距离，那么当距离为i时，只有1 - (n-i)层的白点可以满足条件，又因为白点下面连接的是一颗形如从第二层黑点开始的子树，所以是f[i+1]而不是f[i]，所以，在这种情况下，ans[i]=sum[n-i]f[i+1]，其实就相当于，以这sum[n-i]个白点为根，每个点向下延伸i个距离，有可能到达的白点数】
【2）其实基本原理和第一种情况差不多，只是这时要枚举两个点的路径距离，但是这时的距离不能简单的i+j，因为两个点有可能在一条链上。所以，选择距离h=max(i,j),因为此时的lca为黑点，而通过画图可知：黑点的斐波那契数列比白点的快一层，所以此时满足条件的黑点为sum[n-h+1]，然后以这sum[n-h+1]个黑点为根，每个点从黑儿子延伸i-1个距离、从白儿子延伸j-1个距离，所以ans[i+j]=(sum[n-h+1]-1)f[i]*f[j+1]】

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define mod 123456789
using namespace std;
ll f[5010],sum[5010],ans[10010];
int n;
int main()
{
   // freopen("int.txt","r",stdin);
    //freopen("my.txt","w",stdout);
    int i,j;
    scanf("%d",&n);
    f[1]=f[3]=f[4]=1; f[2]=0; sum[1]=sum[2]=1; sum[3]=2; sum[4]=3;
    for(i=5;i<=n;++i) f[i]=(f[i-1]+f[i-2])%mod,sum[i]=(sum[i-1]+f[i])%mod;
    for(i=1;i<n;++i) 
      ans[i]=(sum[n-i]*f[i+1])%mod;
    for(i=1;i<=n;++i)
     for(j=1;j<=n;++j)
      {
        int x=i+j,r=max(i,j);
        ans[x]=(ans[x]+(sum[n-r+1]-1)*f[i]%mod*f[j+1])%mod;
      }
    n*=2;
    for(i=1;i<=n;++i) printf("%lld ",ans[i]);
    return 0;
}

秒客网