JZOJ 4921. 【NOIP2017提高組模拟12.10】幻魔皇

-##Description

幻魔皇拉比艾爾很喜歡斐波那契樹，他想找到神奇的節點對。所謂斐波那契樹，根是一個白色節點，每個白色節點都有一個黑色節點兒子，而每個黑色節點則有一個白色和一個黑色節點兒子。神奇的節點對則是指白色節點對。請問對于深度為n的斐波那契樹，其中距離為i的神奇節點對有多少個？拉比艾爾需要你對于1<=i<=2n的所有i都求出答案。

Solution

我們設f[i]表示第i層有多少白色節點，g1[i]表示第i層有多少黑色節點，g[i]表示前i層有多少黑色節點。那麼顯然f[i]和g1[i]都是滿足斐波那契數列的形态，是以可以線性求一下，再求一下g[i]。現在分類讨論一下。我們會發現，其實所謂求的f[i]即一個白色點往下走i步後遇到的白色節點數。i從零開始标号，n-1結尾。

1、目前白色節點與它子樹的白色節點距離為i。那麼顯然有 f[i]∑n−ij=0f[j] 。

2、當存在兩個白色節點的lca為黑色節點時，我們設一個白色端點到黑色端點的距離為k,那麼就有ans= ∑i−1k=0f[k+1]∗f[i−k+1]∗g[min(n−i+k,n−k)] 。但這樣會出現重複情況，我們發現一個f[i]=f[i-1]+f[i-2]其實就是一個白色點由一個黑色點下方的白點和黑點轉移得到，是以我們将ans= ∑i−1k=0f[k]∗f[i−k−1]∗g[min(n−i+k,n−k)] ，就沒有重複情況了。

Code

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const ll mo=,maxn=,ni=;
ll f[maxn],g[maxn],g1[maxn];
ll n,i,t,j,k,l,p,ans,q,z;
int main(){
    freopen("raviel.in","r",stdin);freopen("raviel.out","w",stdout);
    scanf("%lld",&n);f[]=;g1[]=;g[]=;
    for (i=;i<=n;i++)
        f[i]=(f[i-]+f[i-])%mo,g1[i]=(g1[i-]+g1[i-])%mo,g[i]=(g[i-]+g1[i])%mo;
    l=*n;n--;
    for (i=;i<=l;i++){
        t=;
        for (j=;j<=n-i;j++)
            t=(t+f[j])%mo;
        ans=t*f[i]%mo;
        if (i>n) p=n;
        else p=i;
        if (i-n>) q=i-n;
        else q=;
        for (k=q;k<p;k++)
            ans=(ans+f[k]*f[i-k-]%mo*g[min(n-k,n-i+k)]%mo)%mo;
        printf("%lld ",ans);
    }   
}