[关闭]
@ysner 2018-06-09T11:37:52.000000Z 字数 1776 阅读 1791

黑红树

DP 概率


题面

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

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

解析

显然不可能在奇数层掉下来,因为他在偶数层时肯定红黑节点个数相等。
看到奇数层
对于偶数层,设表示在该层活着的概率,设表示在该层死掉的概率。(哪像我还把颜色和红黑节点数量差作为状态
然后列转移方程



(肯定要经过一个红节点和一个黑节点,然后两者可以倒过来,则乘
于是第层挂掉的概率为

这玩意儿可以预处理,然后答完询问,总复杂度为
(当然你要在线快速幂我也拦不住)
对于乘爆情况,先把约分掉,保证计算过程中不用约分,就可以直接取模了。
注意楼层有负数

  1. #include<iostream>
  2. #include<cmath>
  3. #include<cstring>
  4. #include<cstdio>
  5. #include<cstdlib>
  6. #include<algorithm>
  7. #define ll unsigned long long
  8. #define re register
  9. #define il inline
  10. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  11. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  12. using namespace std;
  13. ll p,q,las,dp[2][1000005],live[2],die[2],h;
  14. int T,k;
  15. il ll GCD(re ll x,re ll y)
  16. {
  17. if(x<y) swap(x,y);
  18. while(y)
  19. {
  20. re ll tmp=y;
  21. y=x%y;x=tmp;
  22. }
  23. return x;
  24. }
  25. int main()
  26. {
  27. freopen("brtree.in","r",stdin);
  28. freopen("brtree.out","w",stdout);
  29. p=gi();q=gi();T=gi();k=gi();
  30. live[0]=p*(q-p)*2;live[1]=q*q;
  31. re ll gcd=GCD(live[0],live[1]);live[0]/=gcd;live[1]/=gcd;
  32. die[0]=2*p*p+q*q-2*p*q;die[1]=q*q;
  33. gcd=GCD(die[0],die[1]);die[0]/=gcd;die[1]/=gcd;
  34. dp[0][0]=dp[1][0]=1;
  35. 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;
  36. fp(i,1,T)
  37. {
  38. h=gi()-las;
  39. if((h&1)||h<=1) {las=0;puts("0 0");continue;}
  40. las=dp[0][h-2]*die[0]%k;
  41. printf("%lld %lld\n",las,dp[1][h-2]*die[1]%k);
  42. }
  43. fclose(stdin);
  44. fclose(stdout);
  45. return 0;
  46. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注