黑红树

DP 概率

---

题面

$zsy$发现黑红树具有一些独特的性质。

• 这是二叉树,除根节点外每个节点都有红与黑之间的一种颜色。
• 每个节点的两个儿子节点都被染成恰好一个红色一个黑色。
• 这棵树你是望不到头的(树的深度可以到无限大)
• 黑红树上的高度这样定义: $$h_{根节点}=0,h_{son}=h_{fa}+1$$

$zsy$想从树根顺着树往上爬。他有$\frac{p}{q}$的概率到达红色的儿子节点,有 $1-\frac{p}{q}$的概率到达黑色节点。
但是他知道如果自己经过的路径是不平衡的,他会马上摔下来。
一条红黑树上的链是不平衡的,当且仅当红色节点与黑色节点的个数之差大于$1$。
现在他想知道$Q$次他刚好在高度为$h$的地方摔下来的概率的精确值 $\frac{a}{b}$,要求输出$a$,$b$分别对$k$取模后的结果。

• $n\leq10^6,Q\leq10^6,k\leq10^9+7$（$n$代表高度）

解析

$zsy$显然不可能在奇数层掉下来，因为他在偶数层时肯定红黑节点个数相等。
看到奇数层$puts("0\ 0");$
对于偶数层，设$dp[i]$表示在该层活着的概率，设$die[i]$表示在该层死掉的概率。（哪像我还把颜色和红黑节点数量差作为状态）
然后列$DP$转移方程

$$dp[i]=dp[i-2]*\frac{p}{q}*\frac{q-p}{q}*2$$
$$die[i]=dp[i-2]*(\frac{p^2}{q^2}+\frac{(q-p)^2}{q^2})$$
（肯定要经过一个红节点和一个黑节点，然后两者可以倒过来，则乘$2$）
于是第$i$层挂掉的概率为
$$dp[i-2]*(\frac{p^2}{q^2}+\frac{(q-p)^2}{q^2})=dp[i-2]*\frac{2p^2+q^2-2pq}{q^2}$$
这玩意儿可以$O(n)$预处理，然后$O(Q)$答完询问，总复杂度为$O(n)$
（当然你要$O(Qlogn)$在线快速幂我也拦不住)
对于乘爆情况，先把$\frac{2p(q-p)}{q^2},\frac{2p^2+q^2-2pq}{q^2}$约分掉，保证计算过程中不用约分，就可以直接取模了。
注意楼层有负数

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define ll unsigned long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
ll p,q,las,dp[2][1000005],live[2],die[2],h;
int T,k;
il ll GCD(re ll x,re ll y)
{
  if(x<y) swap(x,y);
  while(y)
    {
      re ll tmp=y;
      y=x%y;x=tmp;
    }
  return x;
}
int main()
{
  freopen("brtree.in","r",stdin);
  freopen("brtree.out","w",stdout);
  p=gi();q=gi();T=gi();k=gi();
  live[0]=p*(q-p)*2;live[1]=q*q;
  re ll gcd=GCD(live[0],live[1]);live[0]/=gcd;live[1]/=gcd;
  die[0]=2*p*p+q*q-2*p*q;die[1]=q*q;
  gcd=GCD(die[0],die[1]);die[0]/=gcd;die[1]/=gcd;
  dp[0][0]=dp[1][0]=1;
  fp(i,2,(int)(1e6+2)) dp[0][i]=(dp[0][i-2]*live[0])%k,dp[1][i]=(dp[1][i-2]*live[1])%k;
  fp(i,1,T)
    {
      h=gi()-las;
      if((h&1)||h<=1) {las=0;puts("0 0");continue;}
      las=dp[0][h-2]*die[0]%k;
      printf("%lld %lld\n",las,dp[1][h-2]*die[1]%k);
    }
  fclose(stdin);
  fclose(stdout);
  return 0;
}