結果

問題 No.907 Continuous Kadomatu
ユーザー maspymaspy
提出日時 2020-05-12 15:26:55
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 519 ms
44,424 KB
testcase_01 AC 515 ms
44,292 KB
testcase_02 AC 523 ms
44,548 KB
testcase_03 AC 521 ms
44,548 KB
testcase_04 AC 518 ms
44,548 KB
testcase_05 AC 590 ms
44,804 KB
testcase_06 AC 515 ms
44,544 KB
testcase_07 AC 539 ms
44,680 KB
testcase_08 AC 569 ms
44,416 KB
testcase_09 AC 548 ms
44,160 KB
testcase_10 AC 653 ms
44,548 KB
testcase_11 AC 720 ms
44,172 KB
testcase_12 AC 1,064 ms
44,308 KB
testcase_13 AC 1,153 ms
44,552 KB
testcase_14 AC 1,242 ms
44,220 KB
testcase_15 AC 1,194 ms
44,428 KB
testcase_16 AC 1,202 ms
44,420 KB
testcase_17 AC 1,265 ms
44,976 KB
testcase_18 AC 1,235 ms
44,720 KB
testcase_19 AC 1,283 ms
44,460 KB
testcase_20 AC 532 ms
43,908 KB
testcase_21 AC 531 ms
44,548 KB
testcase_22 AC 532 ms
44,800 KB
testcase_23 AC 1,323 ms
44,976 KB
testcase_24 AC 1,311 ms
44,720 KB
testcase_25 AC 512 ms
44,692 KB
testcase_26 AC 515 ms
44,552 KB
testcase_27 AC 514 ms
44,548 KB
testcase_28 AC 509 ms
44,544 KB
testcase_29 AC 526 ms
44,168 KB
権限があれば一括ダウンロードができます

ソースコード

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