首页 > 代码库 > 【NOIP模拟赛】黑红树 期望概率dp

【NOIP模拟赛】黑红树 期望概率dp

2024-11-12 05:21:39   204人阅读

这是一道比较水的期望概率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==0?y:GCD(y%x,x);
}
inline void Init()
{
    scanf("%lld%lld%lld%lld",&p,&q,&T,&K);
    C=2*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=1;
    while(y)
    {
        if(y&1)ans=ans*x%K;
        y>>=1,x=x*x%K;
    }
    return ans;
}
inline void Work()
{
    LL a=0,b=0;
    while(T--)
    {
        LL h;
        scanf("%lld",&h);
        h-=a;
        if(h==0||h&1)a=b=0,printf("0 0\n");
        else
        {
            LL x=h-2;
            x>>=1;
            a=Pow(C,x)*A%K;
            b=Pow(D,x+1)%K; 
            if(!a)b=0;
            printf("%lld %lld\n",a,b);
        }
    }
}
int main()
{
    Init();
    Work();
}

 

【NOIP模拟赛】黑红树 期望概率dp


联系
我们