Contest Duration: ~ (local time) (100 minutes) Back to Home

Submission #17306923

Source Code Expand

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

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

print(main(LR))```

#### Submission Info

Submission Time 2020-10-10 21:43:03+0900 F - Random Max maspy Python (3.8.2) 600 2521 Byte AC 553 ms 141980 KB

#### Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
 AC × 4
 AC × 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