結果
問題 | No.907 Continuous Kadomatu |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
import sysimport numpy as npread = sys.stdin.buffer.readreadline = sys.stdin.buffer.readlinereadlines = sys.stdin.buffer.readlinesMOD = 10 ** 9 + 7INF = 10 ** 9 + 1N = 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 - Lpower = np.empty((len(X)-1,N+1),np.int64)power[:,0] = 1for 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] = 1p = 1for k, (a, b) in enumerate(zip(A, B)):# 減少列の場合は全体から引くif k % 2 == 0:F *= (-1)F[:, 0] += pF %= MOD# [a,b] へ制限i = np.searchsorted(L, a)j = np.searchsorted(L, b)F[:i] = 0F[j:] = 0# 積分することで累積分布を得る。まずは区間ごとに。F[:, 1:] = F[:, :-1] * inv[1:][None, :] % MODF[:, 0] = 0# 左側の定積分を加えるI = (F * power % MOD).sum(axis=1)np.cumsum(I, out=I)I %= MODp = I[-1]F[1:, 0] += I[:-1]F[1:, 0] %= MOD# 幅で割るc = pow(b - a, MOD - 2, MOD)F = F * c % MODp = p * c % MODprint(p)