【jzoj4921】【幻魔皇】

题目大意

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

解题思路

首先我们发现对于白点只有子树中的白点才可能与它配对（只有一个子节点），对于一个黑点就是在黑白子树中选白点配对。除了深度之外黑点的子树形态都一样白点的子树形态都一样，我们发现以白点为根，每层点数和黑点数是斐波那契额数列。我们可以对白点枚举另一个白点的深度，求有多少个白点有子白点可以达到这个深度，这个也是斐波那契数。对黑点枚举左右子树子节点的深度，用斐波那契数统计对应的黑点白点数即可。

code

#include<cmath>
#include<cstdio>
#include<algorithm>
#define LL long long
#define min(a,b) ((a<b)?a:b)
#define max(a,b) ((a>b)?a:b)
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
using namespace std;
int const maxn=,inf=e9;
int n;LL f[maxn+],s[maxn+],ans[maxn*2+],mo=;
int main(){
    //freopen("raviel.in","r",stdin);
    //freopen("raviel.out","w",stdout);
    freopen("d.in","r",stdin);
    freopen("d.out","w",stdout);
    scanf("%d",&n);
    f[]=f[]=s[]=;s[]=;
    fo(i,,n+)f[i]=(f[i-]+f[i-])%mo,s[i]=(s[i-]+f[i])%mo;
    fo(i,,n){
        ans[i]=(ans[i]+f[n-i]*f[i-])%mo;
        fo(j,,n)ans[i+j]=(ans[i+j]+s[max(,n-max(i,j)-)]*(f[i]-f[i-])%mo*((f[j+]-f[j+]-f[j]+f[j-])%mo))%mo;
    }
    fo(i,,n*2)printf("%lld ",(ans[i]+mo)%mo);
    return ;
}