Atcoder Beginner Contest 280E

Beginner Contest 280E"/>

Atcoder Beginner Contest 280E

Atcoder Beginner Contest 280E - Critical Hit 解题报告

1 题目链接

传送门

2 题目大意

题目：暴击

题目大意：

这里有一个 n n n 滴血的怪物。每一次攻击你有 P P% P 的概率让它失去 2 2 2 滴血，有 ( 100 − P ) % (100-P)\% (100−P)% 的概率让它失去 1 1 1 滴血。如果攻击过后怪物的血量 ≤ 0 \leq 0 ≤0，它就死了。你需要一直攻击怪物直到它死亡。输出攻击次数的期望对 998244353 998244353 998244353 取模的值。

3 解法分析

设 a n s [ i ] ans[i] ans[i] 为怪物剩余生命值为 i i i 时的期望次数。于是有 a n s [ 1 ] = 1 ans[1]=1 ans[1]=1 作为初始条件。

由题，对于 a n s [ i ] ans[i] ans[i]，有 ( 100 − P ) % (100-P)\% (100−P)% 的概率是从 a n s [ i − 1 ] ans[i - 1] ans[i−1] 转移来的，其余都是由 a n s [ i − 2 ] ans[i-2] ans[i−2] 转移来的。

满足转移方程： a n s [ i ] = ( 1 − P 100 ) × ( a n s [ i ] + 1 ) + P 100 × ( a n s [ i − 2 ] + 1 ) ans[i]=(1-\frac P{100})\times(ans[i] + 1)+\frac P{100}\times(ans[i-2] + 1) ans[i]=(1−100P​)×(ans[i]+1)+100P​×(ans[i−2]+1)

上转移方程还需在模 998244353 998244353 998244353 的意义下转移，故再用快速幂求乘法逆元即可。

完结撒花。

4 AC Code

#include <bits/stdc++.h>
#define rep(i, a, b) for (int (i) = (a); (i) <= (b); ++(i))
#define fep(i, a, b) for (int (i) = (a); (i) < (b); ++(i))
#define int long long
#define mod 998244353
#define N 200007
using namespace std;int n, p;
int ans[N];int ksm(int a, int b) {if (b == 0)return 1;if (b & 1)return ksm(a * a % mod, b >> 1) % mod * a % mod;return ksm(a * a % mod, b >> 1) % mod;
}//快速幂求乘法逆元int dfs(int a) {if (a < 1)return 0;if (ans[a])return ans[a];return ans[a] = (1 + dfs(a - 2) * p % mod * ksm(100, mod - 2) % mod + dfs(a - 1) * (100 - p) % mod * ksm(100, mod - 2) % mod) % mod;
}//记忆化搜索signed main() {scanf("%d%d", &n, &p);printf("%lld\n", dfs(n));return 0;
}