CF1096E.The Top Scorer[概率期望]

[ ext{题意:有}n ext{个人,每人有一个分数}a_ileft( a_igeq 0 ight) ,sum{a_i}=s ]

[ ext{假设最高分有}x ext{个,}x ext{个人中的每个人都有}frac{1}{x} ext{的概率获胜} ]

[ ext{第1个人的得分一定在}left[ r,s ight] ext{之内,给出}n,s,r ext{,求他的获胜概率} ]

[ ext{用隔板法,有}left( egin{array}{c} s-r+n-1\ n-1\ end{array} ight) ext{种方案}left( ext{有}r ext{个球已经被固定分给第1个人了} ight) ]

[ ext{求出第1个人作为最高分有多少种方案,再除以总方案数就是获胜概率(要除以同分人数)} ]

[ ext{枚举第1个人得了多少分}x ext{,以及跟他同分的人的个数}y ext{(不包括自己)} ]

[ ext{令}fleft( a,b,c ight) ext{表示}a ext{个非负整数的和是}b, ext{这}a ext{个数的上界是}c ext{的方案数} ]

[ ext{不考虑上界答案是}left( egin{array}{c} b+a-1\ a-1\ end{array} ight) ext{(隔板法)} ]

[gleft( i ight) ext{表示}geq n-i ext{个不合法}left( leq i ext{个合法} ight) ext{的方案数,}hleft( i ight) ext{表示有}n-i ext{个不合法}left( i ext{个合法} ight) ext{的方案数,} ]

[gleft( x ight) =sum_{i=0}^x{left( egin{array}{c} n\ i\ end{array} ight) hleft( i ight)} ]

[ ext{要求}hleft( n ight) , ext{由二项式反演} ]

[hleft( n ight) =sum_{i=0}^n{left( -1 ight) ^{n-i}left( egin{array}{c} n\ i\ end{array} ight) gleft( i ight)} ]

[ ext{对于一个}x ext{,}sum_{y=0}^{n-1}{left( egin{array}{c} n-1\ y\ end{array} ight) fleft( n-y-1,s-xleft( y+1 ight) ,x-1 ight)} ext{就是}x ext{作为最高分的方案数} ]

[ ext{所以答案就是}frac{sum_{x=r}^s{egin{array}{c} sum_{y=0}^{n-1}{frac{left( egin{array}{c} n-1\ y\ end{array} ight) fleft( n-y-1,s-xleft( y+1 ight) ,x-1 ight)}{left( y+1 ight)}}\ end{array}}}{left( egin{array}{c} s-r+n-1\ n-1\ end{array} ight)} ]

#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
inline int Pow(int x, int y) {
  int ret;
  for (ret = 1; y; y >>= 1, x = x * 1ll * x % mod) if (y & 1) ret = ret * 1ll * x % mod;
  return ret % mod;
}
struct Moder {
  int a;
  Moder(int a) : a(a) {}
  Moder() {}
  inline int inv() {return Pow(a, mod - 2);}
  inline void operator += (const int b) {a += b; if (a < 0) a += mod; else if (a >= mod) a -= mod;}
  inline void operator -= (const int b) {a -= b; if (a < 0) a += mod; else if (a >= mod) a -= mod;}
  inline void operator *= (const int b) {a = a * 1ll * b % mod; if (a < 0) a += mod;}
  inline void operator /= (const int b) {a = a * 1ll * Pow(b, mod - 2) % mod; if (a < 0) a += mod;}
  inline void operator += (const Moder &rhs) {*this += rhs.a;}
  inline void operator -= (const Moder &rhs) {*this -= rhs.a;}
  inline void operator *= (const Moder &rhs) {*this *= rhs.a;}
  inline void operator /= (const Moder &rhs) {*this /= rhs.a;}
  inline Moder operator + (const Moder &rhs) const {Moder c = *this; c += rhs; return c;}
  inline Moder operator - (const Moder &rhs) const {Moder c = *this; c -= rhs; return c;}
  inline Moder operator * (const Moder &rhs) const {Moder c = *this; c *= rhs; return c;}
  inline Moder operator / (const Moder &rhs) const {Moder c = *this; c /= rhs; return c;}
  inline void operator = (const int x) {a = x;}
  inline void operator = (const Moder &rhs) {a = rhs.a;}
} fac[10005], ifac[10005];
int n, s, r;
inline Moder C(int n, int m) {
  if (m > n || m < 0) return 0;
  return fac[n] * ifac[n - m] * ifac[m];
}
inline Moder F(int n, int m) {//n个非负整数的和是m的方案数
  if (m < 0) return 0;
  return C(n + m - 1, n - 1);
}

inline Moder F1(int n, int m, int r) { //n个非负整数的和是m 上界是r的方案数
  if (!n && !m) return Moder(1); //这里是合法的,需要return 1
  Moder ret = 0, sign = (n & 1) ? -1 : 1;
  for (int i = 0; i <= n; ++i, sign = sign * -1) if (m - (r + 1) * (n - i) >= 0) ret = ret + sign * C(n, i) * F(n, m - (r + 1) * (n - i));
  // Moder ret = 0, sign = 1;
  // for (int i = 0; i <= n && m - (r + 1) * i >= 0; ++i, sign = sign * -1) ret = ret + sign * C(n, i) * F(n, m - (r + 1) * i);
  //容斥
  return ret;
}

int main() {
  fac[0] = 1;
  for (int i = 1; i <= 5100; ++i) fac[i] = fac[i - 1] * i;
  ifac[5100] = fac[5100].inv();
  for (int i = 5099; i >= 0; --i) ifac[i] = ifac[i + 1] * (i + 1);
  cin >> n >> s >> r;
  Moder ans = 0;
  for (int x = r; x <= s; ++x) {
    for (int y = 0; (y + 1) * x <= s && y + 1 <= n; ++y) {
      int m = n - y - 1, ss = s - (y + 1) * x;
      ans += F1(m, ss, x - 1) * C(n - 1, y) / (y + 1);
    }
  }
  ans /= C(s - r + n - 1, n - 1);
  cout << ans.a;
  return 0;
}
原文地址:https://www.cnblogs.com/storz/p/10229458.html