BZOJ5340: [Ctsc2018]假面【概率+期望】【思维】

LINK

思路

首先考虑减血，直接一个dp做过去，这个部分分不难拿

然后是\(op=1\)的部分

首先因为要知道每个人被打的概率，所以需要算出这个人活着的时候有多少个人活着时概率是什么

那么用\(g_{i,j}\)表示第i个人还活着的时候还有其他的j个人活着的概率

这个东西暴力DP是\(n^3\)的

那么可以考虑优化，用\(f_{i,j}\)表示前i个人有j个人活着的概率

有转移：\(f_{i,j}=f_{i-1,j-1}*(1-p_i)+f_{i-1,j}*p_i\)，其中\(p_i\)表示第i个人已经死了的概率

j等于0特判一下就好了

因为我们用任意i的顺序做f的DP最后的\(f_{n}\)那一行都不会变

所以可以考虑用\(f_n\)逆推回g，因为\(g_{i,j}=f_{n-1,j}\)，我们默认这个时候正在算的i是最后一个

那么根据上面的转移式可以得到\(f_{i-1,j}=\frac{f_{i,j}-(1-p_{now})*f_{i-1,j-1}}{p_{now}}\)

当\(p_{now}=0\)的时候我们发现\(f_{i,j}=f_{i-1,j-1}\)，也就是说最后一个人无论如何是不会死的，那么\(f_{i-1,j}=f_{i,j+1}\)

而当j=0的时候我们又需要特判了，首先入如果\(p_{now}=0\)，\(g_{now,0} = f_{n,1}\)，否则\(g_{now,0}=\frac{f_{n,0}}{p_{now}}\)

剩下的很简单

然后就愉快结束了

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

namespace io {

const int BUFSIZE = 1 << 20;

char ibuf[BUFSIZE], *is = ibuf, *it = ibuf;

char obuf[BUFSIZE], *os = obuf, *ot = obuf + BUFSIZE - 1;

char read_char() {

  if (is == it)

    it = (is = ibuf) + fread(ibuf, 1, BUFSIZE, stdin);

  return *is++;

}

int read_int() {

  int x = 0, f = 1;

  char c = read_char();

  while (!isdigit(c)) {

    if (c == '-') f = -1;

    c = read_char();

  }

  while (isdigit(c)) x = x * 10 + c - '0', c = read_char();

  return x * f;

}

ll read_ll() {

  ll x = 0, f = 1;

  char c = read_char();

  while (!isdigit(c)) {

    if (c == '-') f = -1;

    c = read_char();

  }

  while (isdigit(c)) x = x * 10 + c - '0', c = read_char();

  return x * f;

}

void read_string(char* s) {

  char c = read_char();

  while (isspace(c)) c = read_char();

  while (!isspace(c)) *s++ = c, c = read_char();

  *s = 0;

}

void flush() {

  fwrite(obuf, 1, os - obuf, stdout);

  os = obuf;

}

void print_char(char c) {

  *os++ = c;

  if (os == ot) flush();

}

void print_int(int x) {

  static char q[20];

  if (!x) print_char('0');

  else {

    if (x < 0) print_char('-'), x = -x;

    int top = 0;

    while (x) q[top++] = x % 10 + '0', x /= 10;

    while (top--) print_char(q[top]);

  }

}

void print_ll(ll x) {

  static char q[20];

  if (!x) print_char('0');

  else {

    if (x < 0) print_char('-'), x = -x;

    int top = 0;

    while (x) q[top++] = x % 10 + '0', x /= 10;

    while (top--) print_char(q[top]);

  }

}

struct flusher_t {

  ~flusher_t() {

    flush();

  }

} flusher;

};

using namespace io;

const int Mod = 998244353;

const int N = 210;

int add(int a, int b) {

  return (a += b) >= Mod ? a - Mod : a;

}

int sub(int a, int b) {

  return (a -= b) < 0 ? a + Mod : a;

}

int mul(int a, int b) {

  return 1ll * a * b % Mod;

}

int fast_pow(int a, int b) {

  int res = 1;

  while (b) {

    if (b & 1) res = mul(res, a);

    b >>= 1;

    a = mul(a, a);

  }

  return res;

}

int n, q, m[N], inv[N];

int c[N], res[N];

int p[N][N], f[N][N], g[N][N];

//p[i][j] 第i个人 还有j点血的概率

//f[i][j] 前i个人还有j个人活下来的概率

//g[i][j] 除了第i个人 还有j个人活下来的概率 

int main() {

  n = read_int();

  inv[0] = 1;

  for (int i = 1; i <= n; ++i) {

    m[i] = read_int();

    p[i][m[i]] = 1;

    inv[i] = fast_pow(i, Mod - 2);

  }

  q = read_int();

  while (q--) {

    int op = read_int();

    if (!op) {

      int x = read_int(), p1 = read_int(), p2 = read_int();

      int k = mul(fast_pow(p2, Mod - 2), p1);

      p[x][0] = add(p[x][0], mul(p[x][1], k));

      for (int i = 1; i <= m[x]; ++i) {

        p[x][i] = add(mul(p[x][i + 1], k), mul(p[x][i], sub(1, k)));

      }

    } else {

      int num = read_int();

      for (int i = 1; i <= num; ++i) {

        c[i] = read_int();

      }

      f[0][0] = 1;

      for (int i = 1; i <= num; ++i) {

        f[i][0] = mul(f[i - 1][0], p[c[i]][0]);

        for (int j = 1; j <= i; ++j) {

          f[i][j] = add(mul(f[i - 1][j - 1], sub(1, p[c[i]][0])), mul(f[i - 1][j], p[c[i]][0]));

        }

      }

      for (int i = 1; i <= num; ++i) {

        int invp = fast_pow(p[c[i]][0], Mod - 2);

        if (!p[c[i]][0]) g[i][0] = f[num][1];

        else g[i][0] = mul(f[num][0], invp); //**

        for (int j = 1; j < num; ++j) {

          if (!p[c[i]][0]) g[i][j] = f[num][j + 1];

          else g[i][j] = mul(invp, sub(f[num][j], mul(g[i][j - 1], sub(1, p[c[i]][0]))));

        }

      }

      for (int i = 1; i <= num; ++i) {

        res[i] = 0;

        for (int j = 0; j < num; ++j) {

          res[i] = add(res[i], mul(inv[j + 1], g[i][j]));

        }

        res[i] = mul(res[i], sub(1, p[c[i]][0]));

        print_int(res[i]), print_char(' ');

      }

      print_char('\n');

    }

  }

  for (int i = 1; i <= n; ++i) {

    int cur = 0;

    for (int j = 1; j <= m[i]; ++j) {

      cur = add(cur, mul(p[i][j], j));

    }

    print_int(cur), print_char(' ');

  }

  return 0;

}

巴特西

BZOJ5340: [Ctsc2018]假面【概率+期望】【思维】

思路

最新文章

热门文章