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());
        }
    }

}