直接推式子。
枚举第一次硬币反面朝下的位置。
\[\begin{aligned} E(n)&=\sum_{i=0}^{n-1} p^i(1-p)(k^i+E(n-i-1)) \\ &=\sum_{i=0}^{n-1} (pk)^i(1-p)+\sum_{i=0}^{n-1} p^i(1-p)E(n-i-1)\\ \end{aligned}\]
令 \(f(n)=\sum\limits_{i=0}^{n-1} (pk)^i(1-p),g(n)=\sum\limits_{i=0}^{n-1} p^i(1-p)E(n-i-1)\)
可得：
\[\begin{aligned}f(n)&=p\cdot k\cdot f(n-1)+(1-p)\\ g(n)&=(1-p)f(n-1)+g(n-1)\end{aligned}\]
然后这个式子可以矩阵加速。复杂度 \(\mathcal O(\log n)\)。可能需要卡常。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
#define getchar getchar_unlocked
struct Ios{}io;
template <typename _tp>
Ios &operator >>(Ios &in,_tp &x){
x=0;int w=0;char c=getchar();
for(;!isdigit(c);w|=c=='-',c=getchar());
for(;isdigit(c);x=x*10+(c^'0'),c=getchar());
if(w) x=-x;
return in;
}
typedef long long ll;
const int mod=998244353;
struct Matrix{
int a[4][4];
void clear(){
a[1][1]=0;a[1][2]=0;a[1][3]=0;
a[2][1]=0;a[2][2]=0;a[2][3]=0;
a[3][1]=0;a[3][2]=0;a[3][3]=0;
}
void init(){
a[1][1]=1;a[1][2]=0;a[1][3]=0;
a[2][1]=0;a[2][2]=1;a[2][3]=0;
a[3][1]=0;a[3][2]=0;a[3][3]=1;
}
};
Matrix operator *(Matrix a,Matrix b){
Matrix ans;ans.clear();
ans.a[1][1]=(1ll*a.a[1][1]*b.a[1][1]+1ll*a.a[1][2]*b.a[2][1]+1ll*a.a[1][3]*b.a[3][1])%mod;
ans.a[1][2]=(1ll*a.a[1][1]*b.a[1][2]+1ll*a.a[1][2]*b.a[2][2]+1ll*a.a[1][3]*b.a[3][2])%mod;
ans.a[1][3]=(1ll*a.a[1][1]*b.a[1][3]+1ll*a.a[1][2]*b.a[2][3]+1ll*a.a[1][3]*b.a[3][3])%mod;
ans.a[2][1]=(1ll*a.a[2][1]*b.a[1][1]+1ll*a.a[2][2]*b.a[2][1]+1ll*a.a[2][3]*b.a[3][1])%mod;
ans.a[2][2]=(1ll*a.a[2][1]*b.a[1][2]+1ll*a.a[2][2]*b.a[2][2]+1ll*a.a[2][3]*b.a[3][2])%mod;
ans.a[2][3]=(1ll*a.a[2][1]*b.a[1][3]+1ll*a.a[2][2]*b.a[2][3]+1ll*a.a[2][3]*b.a[3][3])%mod;
ans.a[3][1]=(1ll*a.a[3][1]*b.a[1][1]+1ll*a.a[3][2]*b.a[2][1]+1ll*a.a[3][3]*b.a[3][1])%mod;
ans.a[3][2]=(1ll*a.a[3][1]*b.a[1][2]+1ll*a.a[3][2]*b.a[2][2]+1ll*a.a[3][3]*b.a[3][2])%mod;
ans.a[3][3]=(1ll*a.a[3][1]*b.a[1][3]+1ll*a.a[3][2]*b.a[2][3]+1ll*a.a[3][3]*b.a[3][3])%mod;
return ans;
}
Matrix ans;
int main(){
int T;io>>T;
while(T--){
ll n,k,p;io>>n>>k>>p;
ans.init();
Matrix tmp;tmp.clear();
tmp.a[1][1]=p*k%mod;tmp.a[1][2]=(1-p+mod)%mod;
tmp.a[2][2]=1;
tmp.a[3][1]=(1-p+mod)%mod;tmp.a[3][3]=1;
while(n){
if(n&1) ans=ans*tmp;
n>>=1;tmp=tmp*tmp;
}
Matrix x;x.clear();
x.a[1][3]=1;
ans=x*ans;
printf("%d\n",(ans.a[1][1]+ans.a[1][2])%mod);
}
return 0;
}
原文地址：http://www.cnblogs.com/pref-ctrl27/p/16872501.html
1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，请务用于商业用途!
3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！
8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载
声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性
