結果

問題 No.907 Continuous Kadomatu
ユーザー maspymaspy
提出日時 2020-05-12 15:25:42
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
WA  
実行時間 -
コード長 1,318 bytes
コンパイル時間 284 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 45,180 KB
最終ジャッジ日時 2024-09-13 13:02:01
合計ジャッジ時間 27,064 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 537 ms
43,988 KB
testcase_01 AC 529 ms
44,376 KB
testcase_02 AC 525 ms
43,992 KB
testcase_03 AC 523 ms
44,368 KB
testcase_04 AC 523 ms
43,856 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 AC 545 ms
43,988 KB
testcase_22 AC 551 ms
44,332 KB
testcase_23 WA -
testcase_24 WA -
testcase_25 AC 522 ms
43,984 KB
testcase_26 AC 527 ms
44,492 KB
testcase_27 AC 515 ms
43,988 KB
testcase_28 AC 521 ms
44,496 KB
testcase_29 AC 515 ms
44,232 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) % 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