自动搬运

查看原文

来自洛谷，原作者为

	•́へ•́╬ Unsuccessful Leaving Something attempt

搬运于2025-08-24 22:37:07，当前版本为作者最后更新于2022-11-08 21:47:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

思路

考虑 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
 */