【NOIP模拟赛】黑红树 期望概率dp
2024-08-24 07:50:21
这是一道比较水的期望概率dp但是考场想歪了.......我们可以发现奇数一定是不能掉下来的,因为若奇数掉下来那么上一次偶数一定不会好好待着,那么我们考虑,一个点掉下来一定是有h/2-1个红(黑),h/2+1个黑(红),而且一定是差不多相间的(我就是因为没有看出来这里才会去想组合数,然后......),那么我们发现只要一奇一偶,就可以组成一对,因为偶数一定是平的因此,我们发现在掉下来的那对之前都是红黑或黑红,但是到了这里就是红红或黑黑了,我们只要求出(异色的概率)^(h/2-1)*(同色的概率)就可以了,对于那个约数,我们只要先用数论知识处理出来就好了(一个数与另一个数的最大公约数一定是大的那个数与两个数的差的公约数),然后就放心的快速幂就好了。
特判零!!!!!!!!!!!不特判挂100
#include <cstdio>
using namespace std;
typedef long long LL;
LL p,q,T,K,A,B,C,D;
LL GCD(LL x,LL y)
{
return x==?y:GCD(y%x,x);
}
inline void Init()
{
scanf("%lld%lld%lld%lld",&p,&q,&T,&K);
C=*p*(q-p);
D=B=q*q;
A=D-C;
LL x=GCD(C,D);
C/=x,D/=x,A/=x,B/=x;
}
inline LL Pow(LL x,LL y)
{
LL ans=;
while(y)
{
if(y&)ans=ans*x%K;
y>>=,x=x*x%K;
}
return ans;
}
inline void Work()
{
LL a=,b=;
while(T--)
{
LL h;
scanf("%lld",&h);
h-=a;
if(h==||h&)a=b=,printf("0 0\n");
else
{
LL x=h-;
x>>=;
a=Pow(C,x)*A%K;
b=Pow(D,x+)%K;
if(!a)b=;
printf("%lld %lld\n",a,b);
}
}
}
int main()
{
Init();
Work();
}
最新文章
- Your app declares support for audio in the UIBackgroundModes key in your Info.plist 错误
- ajax待总结项
- 三、jquery操作DOM
- innodb Lock wait timeout exceeded;
- .net 如何引用迅雷组件
- C#引用类型与值类型的比较
- HTML第一天学习笔记
- Apache下Worker模式MPM参数分析
- Java学习笔记--注解
- [Swust OJ 412]--医院设置(floyd算法)
- CacheManager
- 基于vue2.0前端组件库element中 el-form表单 自定义验证填坑
- Egret学习笔记 (Egret打飞机-5.实现子弹对象)
- 报文段、协议、MAC地址
- python基础之类的多态与多态性
- 「Splay」普通平衡树模板
- AtCoder Regular Contest 101
- Note of Python Turtle
- Support For C++11/14/17 Features (Modern C++)
- 2018年长沙理工大学程序设计竞赛 J - 杯子