Submission #17306923

---

Source Code Expand

import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 1_000_000_007

@njit((i8, i8), cache=True)
def mpow(a, n):
    p = 1
    while n:
        if n & 1:
            p = p * a % MOD
        a = a * a % MOD
        n >>= 1
    return p


@njit((i8, ), cache=True)
def fact_table(N):
    N += 1
    fact = np.empty(N, np.int64)
    fact[0] = 1
    for n in range(1, N):
        fact[n] = n * fact[n - 1] % MOD
    fact_inv = np.empty(N, np.int64)
    fact_inv[N - 1] = mpow(fact[N - 1], MOD - 2)
    for n in range(N - 1, 0, -1):
        fact_inv[n - 1] = fact_inv[n] * n % MOD
    inv = np.empty(N, np.int64)
    inv[0] = 0
    inv[1:] = fact[:-1] * fact_inv[1:] % MOD
    return fact, fact_inv, inv

@njit((i8[:], i8[:], i8, i8), cache=True)
def integrate(inv, F, L, R):
    N = len(F)
    G = F * np.arange(N) % MOD
    # 積分
    H = np.zeros(N + 1, np.int64)
    H[1:] = G * inv[1:N + 1] % MOD
    # あとは代入して引く
    ret = 0
    Lp = Rp = 1
    for i in range(1, N + 1):
        Lp = Lp * L % MOD
        Rp = Rp * R % MOD
        ret += (Rp - Lp) * H[i] % MOD
    return ret % MOD

@njit((i8[:], ), cache=True)
def main(LR):
    fact, fact_inv, inv = fact_table(1 << 20)
    L, R = LR[::2], LR[1::2]
    L, R = L + 1, R + 1
    coef = fact[len(L) + 1]
    for i in range(len(L)):
        coef = coef * (R[i] - L[i]) % MOD
    maxL = L.max()
    choose = R > maxL
    L, R = L[choose], R[choose]
    argsort = np.argsort(R)
    L, R = L[argsort], R[argsort]
    N = len(L)
    F = np.zeros(N + 1, np.int64)
    F[0] = 1
    for i in range(N):
        # x-L/R-L倍
        c = mpow(R[i] - L[i], MOD - 2)
        G = F * (-L[i]) % MOD
        G[1:] += F[:-1]
        G %= MOD
        F = G * c % MOD
    ans = 0
    ans += integrate(inv, F, maxL, R[0])
    for i in range(N - 1):
        # [Li, Ri] の寄与を除外
        # (R-L)/(x-L)倍
        c = mpow(-L[i], MOD - 2)
        G = np.zeros_like(F)
        G[0] = F[0] * c % MOD
        for n in range(1, N + 1):
            G[n] = (F[n] - G[n - 1]) * c % MOD
        F = G * (R[i] - L[i]) % MOD
        ans += integrate(inv, F, R[i], R[i + 1])
        # [Ri, Ri+1] で積分
    ans -= 1
    ans %= MOD
    return coef * ans % MOD

N = int(readline())
LR = np.array(read().split(), np.int64)

print(main(LR))

Submission Info

Judge Result