CF1948F 题解

标签：ModLL CF1948F return 题解 res ModInt out OP

对于每个询问，可以把这 \(r - l + 1\) 个袋子包合并成一个 有 \(\sum\limits_{i = l}^r a_i\) 个金币和 \(\sum\limits_{i = l}^r b_i\) 个银币的袋子。\([l, r]\) 外的袋子同理也可以这样合并。

假设 \(sum_a = \sum\limits_{i = 1}^n a_i, sum_b = \sum\limits_{i = 1}^n b_i\)，\(in_a = \sum\limits_{i = l}^r a_i, in_b = \sum\limits_{l = 1}^r b_i\), \(out_a = sum_a - in_a, out_b = sum_b - in_b\)。

那么原问题就是查询 \(in_a + rand(in_b) > out_a + rand(out_b)\) 的概率，其中 \(rand(x)\) 表示 \(x\) 个银币时的随机取值。把上面的式子中符号两边的 \(rand\) 移到同一边，得到：

\[rand(in_b) - rand(out_b) > out_a - in_a \]

观察到 \(in_b + out_b = sum_b\)，那么尝试把 \(rand(in_b) - rand(out_b)\) 变成 \(rand(in_b) + rand(out_b)\)。只需两边同时加上 \(out_b\)，式子变成：

\[rand(in_b) + rand(out_b) > out_a + out_b - in_a \]

接着又有 \(rand(in_b) + rand(out_b) = rand(in_b + out_b) = rand(sum_b)\)，所以最终转化成了：

\[rand(sum_b) > out_a + out_b - in_a \]

其中 \(out_a + out_b - in_a\) 是可以 \(\Theta(1)\) 求得的，设 \(Q = out_a + out_b - in_a\)，那么答案是：

\[\sum\limits_{x = Q + 1}^{sum_b} \binom{sum_b}{x} \times \left(\frac{1}{2}\right)^{n} \]

预处理组合数后缀和即可，复杂度为 \(O(n)\)。

code:

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 2E6 + 5;
template <class T>
T power(T a, long long b) {
  T res = 1;
  for (; b; b >>= 1, a *= a) {
    if (b & 1)
      res *= a;
  } return res;
}
#define C constexpr
#define FC friend constexpr
#define OP operator
template <long long mod>
class ModLL {
  public:
    long long n;
    static long long Mod;
    C ModLL() : n{} {}
    C ModLL(long long x) : n(norm(x % getmod())) {}
    C long long norm(long long x) {
      if (x >= getmod()) x %= getmod();
      if (x <= -getmod()) x %= getmod();
      if (x < 0) x += getmod();
      return x;
    }
    C long long getmod() {return (mod > 0 ? mod : Mod);}
    explicit C OP long long() const {return n;}
    C ModLL OP -() const {ModLL a; a.n = norm(getmod() - n); return a;}
    C ModLL inv() {assert(n != 0); return power((*this), getmod() - 2);}
    C ModLL &OP += (ModLL w) & {n = norm( n + w.n); return (*this);}
    C ModLL &OP -= (ModLL w) & {n = norm( n - w.n); return (*this);}
    C ModLL &OP *= (ModLL w) & {n = norm( 1LL * n * w.n % getmod()); return (*this);}
    C ModLL &OP /= (ModLL w) & {return (*this) *= w.inv();}
    FC ModLL OP + (ModLL a, ModLL b) {ModLL res = a; res += b; return res;}
    FC ModLL OP - (ModLL a, ModLL b) {ModLL res = a; res -= b; return res;}
    FC ModLL OP * (ModLL a, ModLL b) {ModLL res = a; res *= b; return res;}
    FC ModLL OP / (ModLL a, ModLL b) {ModLL res = a; res /= b; return res;}
    FC bool OP == (ModLL a, ModLL b) {return (a.n == b.n);}
    FC bool OP != (ModLL a, ModLL b) {return (a.n != b.n);}
    FC istream &OP >> (istream &is, ModLL &a) {
      long long x = 0; is >> x;
      a = ModLL(x); return is;
    }
    FC ostream &OP << (ostream &os, const ModLL &a) {return (os << (a.n));}
} ; 
template <int mod>
class ModInt {
  public:
    int n;
    static int Mod;
    C ModInt() : n{} {}
    C ModInt(int x) : n(norm(x % getmod())) {}
    C int norm(int x) {
      if (x >= getmod()) x %= getmod();
      if (x <= -getmod()) x %= getmod();
      if (x < 0) x += getmod();
      return x;
    }
    C static int getmod() {return (mod > 0 ? mod : Mod);}
    explicit C OP int() const {return n;}
    C ModInt OP -() const {ModInt a; a.n = norm(getmod() - n); return a;}
    C ModInt inv() const {assert(n != 0); return power((*this), getmod() - 2);}
    C ModInt &OP += (ModInt w) & {n = norm( n + w.n); return (*this);}
    C ModInt &OP -= (ModInt w) & {n = norm( n - w.n); return (*this);}
    C ModInt &OP *= (ModInt w) & {n = norm( 1LL * n * w.n % getmod()); return (*this);}
    C ModInt &OP /= (ModInt w) & {return (*this) *= w.inv();}
    FC ModInt OP + (ModInt a, ModInt b) {ModInt res = a; res += b; return res;}
    FC ModInt OP - (ModInt a, ModInt b) {ModInt res = a; res -= b; return res;}
    FC ModInt OP * (ModInt a, ModInt b) {ModInt res = a; res *= b; return res;}
    FC ModInt OP / (ModInt a, ModInt b) {ModInt res = a; res /= b; return res;}
    FC bool OP == (ModInt a, ModInt b) {return (a.n == b.n);}
    FC bool OP != (ModInt a, ModInt b) {return (a.n != b.n);}
    FC istream &OP >> (istream &is, ModInt &a) {
      int x = 0; is >> x;
      a = ModInt(x); return is;
    }
    FC ostream &OP << (ostream &os, const ModInt &a) {return (os << (a.n));}
} ; 
template <>
long long ModLL <0> :: Mod = (long long)(1E18) + 9;
template <>
int ModInt <0> :: Mod = 998244353;
using P = ModInt <998244353>;
#undef C
#undef FC
#undef OP
signed main(void) {
  ios :: sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n, q; cin >> n >> q;
  vector <int> a(n + 1), b(n + 1);
  for (int i = 1; i <= n; ++i) cin >> a[i];
  for (int i = 1; i <= n; ++i) cin >> b[i];
  vector <int> suma(n + 1), sumb(n + 1);
  for (int i = 1; i <= n; ++i) {
    suma[i] = suma[i - 1] + a[i];
    sumb[i] = sumb[i - 1] + b[i];
  }
  vector <P> comb(sumb[n] + 1), fac(sumb[n] + 1); fac[0] = 1;
  for (int i = 1; i <= sumb[n]; ++i) fac[i] = fac[i - 1] * i;
  comb[sumb[n]] = 1;
  for (int i = sumb[n] - 1; i >= 0; --i) 
    comb[i] = comb[i + 1] + (fac[sumb[n]] / fac[i] / fac[sumb[n] - i]);
  P div = power(P(2), sumb[n]);
  for (int i = 1; i <= q; ++i) {
    int l, r; cin >> l >> r;
    --l;
    int in_a = suma[r] - suma[l], in_b = sumb[r] - sumb[l];
    int out_a = suma[n] - in_a, out_b = sumb[n] - in_b;
    int Q = out_a + out_b - in_a;
    if (Q >= sumb[n]) cout << 0 << ' ';
    else if (Q < 0) cout << 1 << ' ';
    else cout << comb[Q + 1] / div << ' ';
  }
  return 0;
}

标签：ModLL,CF1948F,return,题解,res,ModInt,out,OP
From： https://www.cnblogs.com/CTHOOH/p/18076821