题目

Takahashi布置了一个网页，

给定一个长为24的仅由A和T构成的字符串，表示每天整点能登进这个网页的概率

第i个字母如果是T，表示第i个整点的时候Takahashi有X(1<=X<=99)%的概率能登进去一次，

如果是A，表示第i个整点的时候Aoki有Y(1<=Y<=99)%的概率能登进去一次，

问如果在第一天的0点前把网页挂上去，第n(1<=n<=1e18)次登陆是由Aoki登进去的概率，

答案p/q，对998244353取模

思路来源

官方题解

题解

感觉主要是第一步概率化简就没想到，但是也是很基础的式子

首先要求第一次登陆是发生在第i小时的概率，

即等于第一天在第i小时登陆+第二天在第i小时登陆+...+第无穷天在第i小时成功登陆

而第二天在第i小时登陆的概率=第一天在第i小时登陆的概率*这一整天都没登进去的概率

是一个等比数列求和，考虑计q=这一整天都没登进去的概率

p1=第一天在第i小时登陆的概率

则ans[i]=p1(1+q+q^2+...)=p1*(1-q^无穷)/(1-q)，

又24小时内的事件x、y的概率都大于0，小于1，所以q也在0和1之间，有ans[i]=p1/(1-q)

然后注意到计算p1的时候，实际是默认上一次登录是发生在23点的（0点前）

但有了一次登录之后，对于下一次登录来说，上一次登录就可能发生在[0,23]点的任意一个时刻了

所以，需要预处理dp[i][j]表示上一次登录是在第i时刻时，本次登录是在第j时刻的概率

这个时候，p1这个概率，也就是[i+1,j-1]时刻都登陆失败，而第j时刻登陆成功，

需要考虑跨天的情形

要求第n(n<=1e18)次登录的时候，矩阵快速幂优化一下就可以了，这里写成了类似快速幂的样子

第n次还需要是Aoki登录，所以只统计第n次时，字母是A的答案

代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=65,H=25,mod=998244353;
ll n;
int x,y,q,inv,sum,p[H];
int dp[N][H][H],ans[H],nans[H];
char s[H];
int modpow(int x,int n,int mod){int res=1;for(;n;n>>=1,x=1ll*x*x%mod){if(n&1)res=1ll*res*x%mod;}return res;
}
int cal(){ans[23]=1;for(int i=0;n;n>>=1,i++){if(n&1){memset(nans,0,sizeof nans);for(int j=0;j<24;++j){for(int k=0;k<24;++k){nans[k]=(nans[k]+1ll*ans[j]*dp[i][j][k]%mod)%mod;}}memcpy(ans,nans,sizeof ans);}for(int j=0;j<24;++j){for(int k=0;k<24;++k){for(int l=0;l<24;++l){dp[i+1][j][l]=(dp[i+1][j][l]+1ll*dp[i][j][k]*dp[i][k][l]%mod)%mod;}}}}int res=0;for(int i=0;i<24;++i){if(s[i]=='A'){res=(res+ans[i])%mod;}}return res;
}
int main(){cin>>n>>x>>y;cin>>s;q=1;inv=modpow(100,mod-2,mod);for(int j=0;j<24;++j){ int v=(s[j]=='A')?y:x;p[j]=1ll*v*inv%mod;q=1ll*q*(1-p[j]+mod)%mod;}sum=modpow(1-q+mod,mod-2,mod);//q<1 1*(1-q^n)/(1-q)for(int las=0;las<24;++las){int pre=1;for(int add=0;add<24;++add){int now=(las+add+1)%24;int can=1ll*pre*p[now]%mod;dp[0][las][now]=1ll*sum*can%mod;pre=1ll*pre*(1-p[now]+mod)%mod;}}    cout<<cal()<<endl;return 0;
}