P8229 [AGM 2022 资格赛] 抛硬币

· · 题解

思路

考虑 dp。设 r_i 表示 i 次之后期望剩多少。设 f_i 表示 i 次之后期望吃了多少。

\begin{cases} r_i=r_{i-1}\times kp+1-p\\ f_i=f_{i-1}+r_{i-1}\times(1-p) \end{cases}

解释一下：每次有 p 的概率将 r_{i-1} 的 k 倍贡献给 r_i，有 1-p 的概率吧 r_{i-1} 贡献给 f_i 并吧 1 贡献给 r_i。所以长酱紫。

直接矩阵加速。

code

#include<stdio.h>
#define mod 998244353
#define int long long
inline char nc()
{
    static char buf[99999],*l,*r;
    return l==r&&(r=(l=buf)+fread(buf,1,99999,stdin),l==r)?EOF:*l++;
}
inline void read(int&x)
{
    char c=nc();for(;c<'0'||'9'<c;c=nc());
    for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
int t,n,k,p;
struct __readt__{inline __readt__(){read(t);}}_readt___;
struct matrix
{
    int a[3][3];
    inline void reset(){for(int i=0;i<3;++i)for(int j=0;j<3;a[i][j++]=0);}
    inline void operator*=(const matrix&kkk)
    {
        int ans0=a[0][0]*kkk.a[0][0]+a[0][1]*kkk.a[1][0]+a[0][2]*kkk.a[2][0];
        int ans1=a[0][0]*kkk.a[0][1]+a[0][1]*kkk.a[1][1]+a[0][2]*kkk.a[2][1];
        int ans2=a[0][0]*kkk.a[0][2]+a[0][1]*kkk.a[1][2]+a[0][2]*kkk.a[2][2];
        int ans3=a[1][0]*kkk.a[0][0]+a[1][1]*kkk.a[1][0]+a[1][2]*kkk.a[2][0];
        int ans4=a[1][0]*kkk.a[0][1]+a[1][1]*kkk.a[1][1]+a[1][2]*kkk.a[2][1];
        int ans5=a[1][0]*kkk.a[0][2]+a[1][1]*kkk.a[1][2]+a[1][2]*kkk.a[2][2];
        int ans6=a[2][0]*kkk.a[0][0]+a[2][1]*kkk.a[1][0]+a[2][2]*kkk.a[2][0];
        int ans7=a[2][0]*kkk.a[0][1]+a[2][1]*kkk.a[1][1]+a[2][2]*kkk.a[2][1];
        int ans8=a[2][0]*kkk.a[0][2]+a[2][1]*kkk.a[1][2]+a[2][2]*kkk.a[2][2];
        a[0][0]=ans0%mod;a[0][1]=ans1%mod;a[0][2]=ans2%mod;
        a[1][0]=ans3%mod;a[1][1]=ans4%mod;a[1][2]=ans5%mod;
        a[2][0]=ans6%mod;a[2][1]=ans7%mod;a[2][2]=ans8%mod;
    }
}a,ans;
main()
{
    read(n);read(k);read(p);ans.reset();a.reset();
    ans.a[0][1]=ans.a[0][2]=1;
    a.a[0][0]=a.a[2][2]=1;
    a.a[1][0]=a.a[2][1]=1+mod-p;
    a.a[1][1]=k*p%mod;
    for(;n;n>>=1,a*=a)if(n&1)ans*=a;
    printf("%lld\n",ans.a[0][0]);
    if(--t)main();
}
/*    F   R   1
 *f   1   0   0
 *r  1-p  kp  0
 *1   0  1-p  1
 */