Submission #17306923


Source Code Expand

Copy
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

Submission Time
Task F - Random Max
User maspy
Language Python (3.8.2)
Score 600
Code Size 2521 Byte
Status
Exec Time 553 ms
Memory 141980 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
× 4
× 16
Set Name Test Cases
Sample 01.txt, 02.txt, 03.txt, 04.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt
Case Name Status Exec Time Memory
01.txt 516 ms 141960 KB
02.txt 496 ms 141268 KB
03.txt 496 ms 141392 KB
04.txt 496 ms 141348 KB
11.txt 505 ms 141396 KB
12.txt 505 ms 141296 KB
13.txt 504 ms 141360 KB
14.txt 499 ms 141464 KB
15.txt 531 ms 141408 KB
16.txt 503 ms 141980 KB
17.txt 549 ms 141196 KB
18.txt 549 ms 141296 KB
19.txt 514 ms 141552 KB
20.txt 540 ms 141540 KB
21.txt 542 ms 141552 KB
22.txt 553 ms 141952 KB