本文主要是介绍（AtCoder Beginner Contest 333）--- F - Bomb Game 2 --- 题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
F - Bomb Game 2：
题目大意：
思路解析：
这道题一读题面就知道他是个概率dp，假如有 i 个人我们要输出这i个人每个人最后能够留下的概率。
设状态dp[i][j] 表示当前有i个人，目标人物位于这i个人中的第j个位置。如果我们通过dp[i][j]往前推，让dp[1][1]为目标状态，这样一次dp就只能得到一个人的答案概率。
但是如果我们让dp[1][1]为初始状态，dp[i][j]表示当前有i个人，目标人物位于这i个人中的第j个位置。然后转移过程改为有1/2的概率在当前队列的第一个位置加入一个人，有1/2的概率将当前队列的最后一个人移动到当前队列的队首。
dp[i][j] = (dp[i-1][j-1] + dp[i][j-1) * 1/2 %mod; 这里*1/2需要用到逆元。 j>=2;
dp[i][1] += dp[i-1][i-j+1] * pt[i][j]。j>=2 这里需要乘以 pt[i][j]的概率。
例如 dp[3][1] += dp[2][2] * pt[3][2].
dp[2][2] 代表当前有两个人目标人物在第二个， 添加一个人后变为当前有三个人，目标人物在第三个，我们需要通过移动来讲目标人物移动到第一个， pt[i][j] 就代表这次移动的概率。
代码实现：
import java.io.*;
import java.math.BigInteger;
import java.util.*;public class Main {static int mod = 998244353;public static void main(String[] args) throws IOException {int n = input.nextInt();long inv2 = pow(2);long[] p = new long[n+1];p[0] = 1;for (int i = 1; i <= n; i++) {p[i] = p[i - 1] * inv2 % mod;}long[][] pt = new long[n +1][n+1];for (int i = 2; i <= n; i++) {long mu = pow(((1 - p[i]) + mod) % mod);for (int j = 2; j <= i; j++) pt[i][j] = p[j] * mu % mod;}long[][] dp = new long[n + 1][n + 1];dp[1][1] = 1;for (int i = 2; i <= n; i++) {for (int j = 2; j <= i; j++) {dp[i][1] = (dp[i][1] + dp[i - 1][i - j + 1] * pt[i][j] % mod) % mod;}for (int j = 2; j <= i; j++) {dp[i][j] = (dp[i][j - 1] + dp[i-1][j - 1]) * inv2% mod;}}for (int i = 1; i <= n; i++) {out.print(dp[n][i] + " ");}out.flush();out.close();br.close();}public static long pow(long a){long b = mod - 2;long res = 1;while (b > 0){if ((b & 1) == 1) res = (res * a) % mod;a = (a * a) % mod;b >>= 1;}return res;}static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static Input input = new Input(System.in);static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static class Input {public BufferedReader reader;public StringTokenizer tokenizer;public Input(InputStream stream) {reader = new BufferedReader(new InputStreamReader(stream), 32768);tokenizer = null;}public String next() {while (tokenizer == null || !tokenizer.hasMoreTokens()) {try {tokenizer = new StringTokenizer(reader.readLine());} catch (IOException e) {throw new RuntimeException(e);}}return tokenizer.nextToken();}public String nextLine() {String str = null;try {str = reader.readLine();} catch (IOException e) {// TODO 自动生成的 catch 块e.printStackTrace();}return str;}public int nextInt() {return Integer.parseInt(next());}public long nextLong() {return Long.parseLong(next());}public Double nextDouble() {return Double.parseDouble(next());}public BigInteger nextBigInteger() {return new BigInteger(next());}}}
这篇关于（AtCoder Beginner Contest 333）--- F - Bomb Game 2 --- 题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
