結果

問題 No.907 Continuous Kadomatu
ユーザー maspy
提出日時 2020-05-12 15:26:55
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 1,323 ms / 2,000 ms
コード長 1,327 bytes
コンパイル時間 112 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 44,976 KB
最終ジャッジ日時 2024-09-13 13:03:19
合計ジャッジ時間 25,005 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import numpy as np

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

MOD = 10 ** 9 + 7
INF = 10 ** 9 + 1

N = int(readline())
m = map(int, read().split())
A,B = zip(*zip(m,m))

X = sorted(set((0,) + A + B + (INF,)))
L = np.array(X[:-1])
R = np.array(X[1:])

inv = np.array([pow(x,MOD-2,MOD) for x in range(N+1)])

dx = R - L
power = np.empty((len(X)-1,N+1),np.int64)
power[:,0] = 1
for i in range(N):
    power[:,i+1] = power[:,i] * dx % MOD

# 区間ごとに、累積分布関数を (x - L) の多項式で持つ
F = np.zeros((len(X) - 1,N+1),np.int64)
F[-1,0] = 1
p = 1

for k, (a, b) in enumerate(zip(A, B)):
    # 減少列の場合は全体から引く
    if k % 2 == 0:
        F *= (-1)
        F[:, 0] += p
        F %= MOD
    # [a,b] へ制限
    i = np.searchsorted(L, a)
    j = np.searchsorted(L, b)
    F[:i] = 0
    F[j:] = 0
    # 積分することで累積分布を得る。まずは区間ごとに。
    F[:, 1:] = F[:, :-1] * inv[1:][None, :] % MOD
    F[:, 0] = 0
    # 左側の定積分を加える
    I = (F * power % MOD).sum(axis=1)
    np.cumsum(I, out=I)
    I %= MOD
    p = I[-1]
    F[1:, 0] += I[:-1]
    F[1:, 0] %= MOD
    # 幅で割る
    c = pow(b - a, MOD - 2, MOD)
    F = F * c % MOD
    p = p * c % MOD

print(p)
0