P8229 [AGM 2022 资格赛] 抛硬币
Perta
·
·
题解
[2022.3.31] 更正了一些公式错误。
[2022.10.11] 回来修锅+简化题解。
[2023.1.14] 修复部分代码错误。
题意简述
### 思路
对于每次操作，$x$ 的贡献为 $xP_2$，其中 $P_2$ 表示变成 $1$ 的概率。初始时 $x=1$，一次操作后，$x=kP_1+P_2$。
***
由于 $x$ 是由自身转移而来，我们可以列出递推式：
$$
x_i=kP_1\times x_{i-1}+P_2
$$
令 $a=kP_1$，将递推式化简：
$$
x_i=a^i+P_2\sum_{j=0}^{i-1}a^j
$$
$$
\left\{
\begin{aligned}
& x_i=a^i+\frac{a^i-1}{a-1}P_2,&a\neq1 \\
& x_i=1+iP_2,&a=1
\end{aligned}
\right.
$$
***
我们还要想办法将这个 $n$ 的复杂度给化掉。
将 $x$ 代入，我们要求的便是：
$$
\left\{
\begin{aligned}
& P_2(\sum_{i=1}^na^{i-1}+\frac{a^{i-1}-1}{a-1}P_2),& a\neq1\\
& P_2(\sum_{i=1}^n1+(i-1)P_2),& a=1
\end{aligned}
\right.
$$
注意是 $i-1$ 不是 $i$，此处 $x_0=1$。
***
当 $a\neq1$ 时：
$$
P_2(\sum_{i=0}^{n-1}a^i+P_2\sum_{i=0}^{n-1}\frac{a^i-1}{a-1})
$$
$$
P_2(\sum_{i=0}^{n-1}a^i+P_2\frac{\sum_{i=0}^{n-1}a^i-n}{a-1})
$$
令 $S_n=\sum_{i=0}^{n-1}a^i=\frac{a^n-1}{a-1}$，
$$
P_2(S_n+P_2\frac{S_n-n}{a-1})
$$
***
再看 $a=1$ 的情况：
$$
P_2\sum_{i=1}^n(1+(i-1)\times P_2)
$$
$$
P_2(n+P_2\sum_{i=0}^{n-1}i)
$$
综上所述，答案 $Ans$：
$$
\left\{
\begin{aligned}
& Ans=P_2(S_n+P_2\frac{S_n-n}{a-1}),& a\neq1\\
& Ans=P_2(n+P_2\sum_{i=0}^{n-1}i),& a=1
\end{aligned}
\right.
$$
时间复杂度 $O(T\log n)$。
### 代码
遇上大数乘除模总担心爆精度，所以记得勤取模。还要记得判断负数取模的情况。
```
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
int t,n,k,p1,p2,ans;
int ksm(int x,int y)
{
int res=1;
while(y)
{
if(y&1) res=res*x%mod;
x=x*x%mod;
y>>=1;
}
return res;
}
signed main()
{
scanf("%lld",&t);
while(t--)
{
scanf("%lld%lld%lld",&n,&k,&p1);
p2=(1-p1+mod)%mod;
int a=k*p1%mod,inv=ksm((a-1+mod)%mod,mod-2),Sn=(ksm(a,n)-1+mod)*inv%mod;
n%=mod;
if(a==1) ans=(n*p2%mod+n*(n-1)/2%mod*p2%mod*p2%mod)%mod;
else ans=(Sn+p2*(Sn-n+mod)%mod*inv%mod)%mod*p2%mod;
printf("%lld\n",ans);
}
return 0;
}
```
***
完结撒花owo。