HHKB 2020 F - Random Max

各 $i = 1, \ldots , n$ について確率変数 $X _ {i}$ が独立に $[L _ {i}, R _ {i}]$ 上の一様分布に従うとき，$Y = \mathrm{max} \{ X _ {1} , \ldots , X _ {n} \}$ の期待値を求める．

F - Random Max

解説

$Y$ の分布関数は $$ F(x) = P(Y \leq x) = \prod _ {i = 1} ^ {n} P(X _ {i} \leq x) $$ で，期待値は $$ \int _ {0} ^ {10 ^ {9}} x F ' (x) dx = \left[ x F(x) \right] _ {0} ^ {10 ^ {9}} - \int _ {0} ^ {10 ^ {9}} F (x) dx $$ で求められる．
$x \leq \mathrm{max}L$ では $F(x) = 0$ であり，$x \geq R _ {i}$ なら $P(X _ {i} \leq x) = 1 $ だから，$\mathrm{max}L$ より大きい $R _ {i}$ らをソートし，新たに $R _ {1}, \ldots, R _ {k}$ と番号をつけ，そこで積分区間を区切る．
最初，$[R _ {k}, 10 ^ {9}]$ では $F(x) = 1$ であり，左の区間に移動するごとに $$ P(X _ {i} \leq x) = \frac{x - L _ {i}}{R _ {i} - L _ {i}}\ (L _ {i} \leq x \leq R _ {i}) $$ が $F(x)$ にかけられていく．
多項式の掛け算と積分ができれば答えが求められる．

実装

提出 #17347877 - HHKB プログラミングコンテスト 2020

最終的に $10 ^ 9 + 7$ で割ったあまりを求めたいので，mod計算可能な整数型と多項式型を使った．

Mint (mod int) 型

(a + b) % MOD のような計算が a + b だけでできるようになっている．

class Mint:
    def __init__(self, val, MOD=10 ** 9 + 7):
        self.val = val % MOD
        self.MOD = MOD

    def __repr__(self):
        return str(self.val)

    def __add__(self, other):
        return Mint((self.val + other.val) % self.MOD)

    def __sub__(self, other):
        return Mint((self.val - other.val) % self.MOD)

    def __mul__(self, other):
        return Mint((self.val * other.val) % self.MOD)

    def __truediv__(self, other):
        return self.__mul__(other.__inv__())

    def __pow__(self, p):
        return Mint(pow(self.val, p, self.MOD))

    def __inv__(self):
        return Mint(pow(self.val, self.MOD - 2, self.MOD))

多項式型

p = Polynomial([1, 2, 3]) で多項式 $1 + 2x + 3 x ^ {2}$ が宣言できる．また，多項式同士の積が p * q で計算でき，p.substitute(2) 等で $x = 2$ の代入，p.integrate(1, 2) 等で積分ができる．

class Polynomial:
    def __init__(self, coefficients):
        self.coefficients = coefficients

    def __mul__(self, other):
        m = len(self.coefficients)
        n = len(other.coefficients)
        coefficients = [Mint(0)] * (m + n - 1)
        for i, a in enumerate(self.coefficients):
            for j, b in enumerate(other.coefficients):
                coefficients[i + j] = coefficients[i + j] + a * b
        return Polynomial(coefficients)

    def substitute(self, x):
        y = Mint(0)
        for i, a in enumerate(self.coefficients):
            y = y + a * x ** i
        return y

    def antiderivative(self):
        coefficients = [Mint(0)] * (len(self.coefficients) + 1)
        for i, a in enumerate(self.coefficients):
            coefficients[i + 1] = a / Mint(i + 1)
        return Polynomial(coefficients)

    def integrate(self, a, b):
        P = self.antiderivative()
        return P.substitute(b) - P.substitute(a)

本編

INF = 10 ** 9
n = int(input())
L, R = [], []
for i in range(n):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)
maxL = max(L)
IDs = [i for i in range(n) if maxL < R[i]]
IDs.sort(key=lambda i: R[i], reverse=True)
L = [Mint(l) for l in L]
R = [Mint(r) for r in R]
ans = Mint(INF)
b = Mint(INF)
poly = Polynomial([Mint(1)])
for i in IDs:
    a = R[i]
    ans = ans - poly.integrate(a, b)
    poly = poly * Polynomial([Mint(-1) * L[i] / (R[i] - L[i]), Mint(1) / (R[i] - L[i])])
    b = a
a = Mint(maxL)
ans = ans - poly.integrate(a, b)
for i in range(n):
    ans = ans * Mint(i + 2) * (R[i] - L[i])
print(ans)