[ARC174C] Catastrophic Roulette 题解
STUDENT00
·
·
题解
传送门：Luogu / AtCoder。
首次参赛 ARC，1100 分，749 名（菜就多练，越练越菜）。C 题是 ABCD 四题里我唯一不会的，ABD 共计 1h 全 AC，C 题 10min 无思路，就被赶进房间、被逼迫睡觉了，wuwu……
emem，咱们切入正题。
求期望值？DP，启动！显然，数据范围 1\le n\le 10^6 只允许我们使用 O(n) DP。你根本不知道这个游戏要玩几轮（如果双方“默契”地一直抽 1，轮数就 =\infty），所以不能把轮数作为状态维度。
显然，抽到过的卡牌数量相同，则期望值相同，否则不同，具体抽到哪些卡牌无需理会。尝试用“抽到过的卡牌数量”作 DP 维度。
用 f1_i 表示“抽到过的卡牌数量变成 i 的那刻，先手的罚款期望值”。
用 f2_i 表示“抽到过的卡牌数量变成 i 的那刻，后手的罚款期望值”。
边界：f1_1=f2_1=0。
转移方程：f1_{i+1}=f1_i+A。
那怎么求 $A$ 呢？
显然，$A$ 是一条级数式，而常数项相同的级数式较易求和。设 $h1=$ 抽到过的卡牌数量变成 $i$ 后轮到先手的概率，$h2=$ 抽到过的卡牌数量变成 $i$ 后轮到后手的概率，则有：
$A=(h1\times \frac{i}{n}+h1\times\frac{i}{n}\times\frac{i}{n}\times\frac{i}{n}+...)+(h2\times\frac{i}{n}\times\frac{i}{n}+h2\times\frac{i}{n}\times\frac{i}{n}\times \frac{i}{n}\times\frac{i}{n})
\>\>\>\>=h1\times\frac{i}{n}\times(1+(\frac{i}{n})^2+(\frac{i}{n})^4+...)+h2\times(\frac{i}{n})^2\times(1+(\frac{i}{n})^2+(\frac{i}{n})^4+...)
设 p=\frac{i}{n}，则 1+(\frac{i}{n})^2+(\frac{i}{n})^4+...=\frac{1}{1-p^2}。
代入原式，$f1_{i+1}=f1_i+h1\times\frac{p}{1-p^2}+h2\times\frac{p^2}{1-p^2}$。
同理，$f2_{i+1}=f2_i+h2\times\frac{p}{1-p^2}+h1\times\frac{p^2}{1-p^2}$。
问题：怎么求 $h1$，$h2$ 呢？
简单，DP，启动！
用 $h1_i$ 表示“**抽到过的卡牌数量变成 $i$ 后轮到先手的概率**”。
用 $h2_i$ 表示“**抽到过的卡牌数量变成 $i$ 后轮到后手的概率**”。
边界：$h1_1=0,h2_1=1$。
转移方程推导：
$h1_{i+1}=(h1_i\times p\times (1-p)+h1_i\times p\times p\times p\times (1-p)+...)+(h2_i\times (1-p)+h2_i\times p\times p\times (1-p)+...)
\>\>\>\>\>\>\>\>\>\>\>=h1\times p\times (1-p)\times \frac{1}{1-p^2}+h2\times (1-p)\times \frac{1}{1-p^2}
同理，$h2_{i+1}=\frac{1}{1+p}\times (h2\times p+h1)$。
最终答案为 $(f1_n,f2_n)$。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
const int mod=998244353;
typedef long long ll;
int n;
int h1[N],h2[N],f1[N],f2[N];
int qpow(int a,int b){
int res=1;
while(b){
if(b&1) res=(ll)res*a%mod;
a=(ll)a*a%mod;
b>>=1;
}
return res;
}
int inv(int x){
return qpow(x,mod-2);
}
int main(){
scanf("%d",&n);
h2[1]=1;
for(int i=1;i<n;i++){
int p=(ll)i*inv(n)%mod;
h1[i+1]=(h2[i]+(ll)h1[i]*p)%mod*inv(1+p)%mod;
h2[i+1]=(h1[i]+(ll)h2[i]*p)%mod*inv(1+p)%mod;
f1[i+1]=(f1[i]+(h1[i]+(ll)h2[i]*p)%mod*p%mod*inv((1-(ll)p*p%mod+mod)%mod)%mod)%mod;
f2[i+1]=(f2[i]+(h2[i]+(ll)h1[i]*p)%mod*p%mod*inv((1-(ll)p*p%mod+mod)%mod)%mod)%mod;
}
printf("%d %d",f1[n],f2[n]);
return 0;
}
```