結果
問題 | No.907 Continuous Kadomatu |
ユーザー |
|
提出日時 | 2019-04-23 18:59:09 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 515 ms / 2,000 ms |
コード長 | 3,039 bytes |
コンパイル時間 | 2,176 ms |
コンパイル使用メモリ | 79,896 KB |
実行使用メモリ | 44,908 KB |
最終ジャッジ日時 | 2024-10-13 12:57:12 |
合計ジャッジ時間 | 11,224 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 25 |
ソースコード
// O(N^3)の解// 制約の侵害の有無を確認import java.util.Arrays;import java.util.HashSet;import java.util.Scanner;class Main {public static void main(String[] args) {new Main().run();}final long MOD = 1_000_000_000 + 7;long[] karamatsu_prob = new long[400];long[] fac = new long[400];long[] ifac = new long[400];long pow(long a, long n) {long ret = 1;for (; n > 0; n >>= 1, a = a * a % MOD) {if (n % 2 == 1) {ret = ret * a % MOD;}}return ret;}long inv(long a) {return pow(a, MOD - 2);}{fac[0] = fac[1] = 1;ifac[0] = ifac[1] = 1;for (int i = 2; i < fac.length; ++i)fac[i] = fac[i - 1] * i % MOD;for (int i = 2; i < ifac.length; ++i) {ifac[i] = inv(fac[i]);}}long comb(int n, int k) {return fac[n] * ifac[k] % MOD * ifac[n - k] % MOD;}{karamatsu_prob[0] = 1;karamatsu_prob[1] = 1;for (int i = 2; i < karamatsu_prob.length; ++i) {for (int j = 0; j <= i - 1; j += 2) {karamatsu_prob[i] += karamatsu_prob[j] * karamatsu_prob[i - j - 1] % MOD * comb(i - 1, j) % MOD;karamatsu_prob[i] %= MOD;}}for (int i = 0; i < karamatsu_prob.length; ++i) {karamatsu_prob[i] = karamatsu_prob[i] * ifac[i] % MOD;}}void run() {Scanner sc = new Scanner(System.in);int N = sc.nextInt();if (!(3 <= N && N <= 200))throw new AssertionError();++N;long[] l = new long[N];long[] r = new long[N];HashSet<Long> set = new HashSet<>();for (int i = 1; i < N; ++i) {l[i] = sc.nextLong();r[i] = sc.nextLong();if (!(1 <= l[i] && r[i] <= 1e9 && l[i] < r[i]))throw new AssertionError();set.add(l[i]);set.add(r[i]);// [l[i],r[i])}set.add((long) 1e9);set.add((long) 1e9 + 1);l[0] = (long) 1e9;r[0] = (long) 1e9 + 1;long[] a = new long[set.size()];int sz = 0;for (long v : set) {a[sz] = v;++sz;}Arrays.sort(a);// [a[i],a[i+1]]long[][] p = new long[N][sz];for (int i = 0; i < N; ++i) {for (int j = 0; j + 1 < sz; ++j) {if (!(l[i] <= a[j] && a[j + 1] <= r[i]))continue;p[i][j] = (a[j + 1] - a[j]) * inv(r[i] - l[i]) % MOD;}}long[][] prob = new long[N][sz];long[][] pending = new long[N][sz];prob[0][sz - 2] = 1;for (int t = 0; t < N; ++t) {for (int src = 0; src + 1 < sz; ++src) {long prob_cur = pending[t][src];for (int i = 0; i + t < N; ++i) {prob_cur = prob_cur * p[t + i][src] % MOD;prob[t + i][src] += prob_cur * karamatsu_prob[i + 1] % MOD;prob[t + i][src] %= MOD;}for (int dst = 0; dst + 1 < sz; ++dst) {if ((t % 2 == 1 && src >= dst) || (t % 2 == 0 && src <= dst))continue;if (t + 1 < N) {pending[t + 1][dst] += prob[t][src] % MOD;pending[t + 1][dst] %= MOD;}}}}long ans = 0;for (int i = 0; i < prob[N - 1].length; ++i)ans = (ans + prob[N - 1][i]) % MOD;System.out.println(ans);}void tr(Object... objects) {System.out.println(Arrays.deepToString(objects));}}