2022杭电多校（三）

2022杭电多校（三）

一、比赛小结

比赛链接：Problems (hdu.edu.cn)

二、题目分析及解法（基础题） 1001、Equipment Upgrade

题目链接：Problem - 7162 (hdu.edu.cn)

题意：

一共有 n n n 级，在第 i i i 级时，升级到 i + 1 i+1 i+1 级的概率为 p i p_i pi​ ，且要被花费 c i c_i ci​ 元，并且还有 ( 1 − p i ) ω j ∑ k = 1 i ω k \displaystyle (1-p_i)\frac{\omega_j}{\sum_{k=1}^i\omega_k} (1−pi​)∑k=1i​ωk​ωj​​ 的概率降到第 i − j i-j i−j 级，求从 0 0 0 级升到 n n n 级的期望花费。

题解：

我们先来推下式子：

E n = 0 E_n=0 En​=0

E i = c i + p i ⋅ E i + 1 + 1 − p i ∑ j = 1 i ω j ⋅ ( ∑ j = 1 i ω j ⋅ E i − j ) \displaystyle E_i=c_i+p_i \cdot E_{i+1}+\frac{1-p_i}{\sum_{j=1}^i\omega_j}\cdot (\sum_{j=1}^i\omega_j\cdot E_{i-j}) Ei​=ci​+pi​⋅Ei+1​+∑j=1i​ωj​1−pi​​⋅(j=1∑i​ωj​⋅Ei−j​)

E i + 1 = E i − c i − 1 − p i ∑ j = 1 i ω j ⋅ ( ∑ j = 1 i ω j ⋅ E i − j ) p i \displaystyle E_{i+1}=\frac{E_i-c_i-\frac{1-p_i}{\sum_{j=1}^i\omega_j}\cdot (\sum_{j=1}^i{\omega_j\cdot E_{i-j}})}{p_i} Ei+1​=pi​Ei​−ci​−∑j=1i​ωj​1−pi​​⋅(∑j=1i​ωj​⋅Ei−j​)​

然后设 E i = a i ⋅ E 0 + b i E_i=a_i\cdot E_0+b_i Ei​=ai​⋅E0​+bi​ ，则有：

a 0 = 1 ,   b 0 = 0 a_0=1, \ b_0=0 a0​=1, b0​=0

a i + 1 = a i − 1 − p i ∑ j = 1 i ω j ⋅ ( ∑ j = 1 i ω j ⋅ a i − j ) p i \displaystyle a_{i+1}=\frac{a_i-\frac{1-p_i}{\sum_{j=1}^i\omega_j}\cdot (\sum_{j=1}^i\omega_j \cdot a_{i-j})}{p_i} ai+1​=pi​ai​−∑j=1i​ωj​1−pi​​⋅(∑j=1i​ωj​⋅ai−j​)​

b i + 1 = b i − c i − 1 − p i ∑ j = 1 i ω j ⋅ ( ∑ j = 1 i ω j ⋅ b i − j ) p i \displaystyle b_{i+1}=\frac{b_i-c_i-\frac{1-p_i}{\sum_{j=1}^i\omega_j}\cdot (\sum_{j=1}^i\omega_j\cdot b_{i-j})}{p_i} bi+1​=pi​bi​−ci​−∑j=1i​ωj​1−pi​​⋅(∑j=1i​ωj​⋅bi−j​)​

这个递推有卷积的形式，因此可以用 分治+NTT 来做，分治NTT已经变成常识了（悲

代码：

#include 
#define int long long
using namespace std;
namespace poly {
typedef long long ll;
const int mod = 998244353;
const int maxn = 1e6 + 10;
ll invi[maxn];
// 记得先init()!!!!!!!!!
void init() {
  invi[1] = 1;
  for (int i = 2; i >= 1;
    x = x * x % mod;
  }
  return ans;
}
// 二次剩余
ll modsqrt(ll x) {
  if (mod == 2) return x % mod;
  if (quickpow(x, mod - 1 >> 1) != 1) return -1;
  ll ans = 0;
  if (mod % 4 == 3)
    ans = quickpow(x, mod + 1 >> 2);
  else {
    ll b;
    for (b = rand() % mod; quickpow(b, mod - 1 >> 1) == 1; b = rand() % mod)
      ;
    ll i = mod - 1 >> 1, k = 0;
    do {
      i >>= 1;
      k >>= 1;
      if ((quickpow(x, i) * quickpow(b, k) + 1) % mod == 0) k += (mod - 1 >> 1);
    } while (i % 2 == 0);
    ans = quickpow(x, i + 1 >> 1) * quickpow(b, k >> 1) % mod;
  }
  if (ans * 2 > mod) ans = mod - ans;
  return ans;
}
// 蝴蝶变换
void change(ll* a, int len) {
  static int rev[maxn];
  rev[0] = 0;
  for (int i = 0; i > 1] >> 1);
    if (i & 1) rev[i] |= len >> 1;
  }
  for (int i = 0; i  INTT , O(nlogn)
void NTT(ll* a, int len, int flag) {
  change(a, len);
  for (int h = 2; h