結果

問題 No.907 Continuous Kadomatu
ユーザー maspymaspy
提出日時 2020-05-12 15:26:55
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 992 ms / 2,000 ms
コード長 1,327 bytes
コンパイル時間 84 ms
コンパイル使用メモリ 11,056 KB
実行使用メモリ 31,980 KB
最終ジャッジ日時 2023-10-11 14:21:21
合計ジャッジ時間 16,103 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 129 ms
29,436 KB
testcase_01 AC 127 ms
29,476 KB
testcase_02 AC 127 ms
29,440 KB
testcase_03 AC 126 ms
29,416 KB
testcase_04 AC 127 ms
29,636 KB
testcase_05 AC 206 ms
29,944 KB
testcase_06 AC 130 ms
29,432 KB
testcase_07 AC 149 ms
29,760 KB
testcase_08 AC 182 ms
30,016 KB
testcase_09 AC 161 ms
29,768 KB
testcase_10 AC 272 ms
30,200 KB
testcase_11 AC 345 ms
30,348 KB
testcase_12 AC 714 ms
31,304 KB
testcase_13 AC 784 ms
31,576 KB
testcase_14 AC 885 ms
31,744 KB
testcase_15 AC 852 ms
31,808 KB
testcase_16 AC 859 ms
31,820 KB
testcase_17 AC 930 ms
31,980 KB
testcase_18 AC 873 ms
31,752 KB
testcase_19 AC 921 ms
31,844 KB
testcase_20 AC 143 ms
29,584 KB
testcase_21 AC 146 ms
29,428 KB
testcase_22 AC 145 ms
29,456 KB
testcase_23 AC 992 ms
31,940 KB
testcase_24 AC 992 ms
31,976 KB
testcase_25 AC 127 ms
29,484 KB
testcase_26 AC 131 ms
29,576 KB
testcase_27 AC 127 ms
29,432 KB
testcase_28 AC 127 ms
29,408 KB
testcase_29 AC 130 ms
29,440 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