結果

問題 No.907 Continuous Kadomatu
ユーザー maspymaspy
提出日時 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)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0