結果
問題 | No.907 Continuous Kadomatu |
ユーザー |
![]() |
提出日時 | 2019-10-11 22:12:06 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 221 ms / 2,000 ms |
コード長 | 3,596 bytes |
コンパイル時間 | 926 ms |
コンパイル使用メモリ | 102,724 KB |
実行使用メモリ | 9,500 KB |
最終ジャッジ日時 | 2024-11-25 07:42:14 |
合計ジャッジ時間 | 3,597 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 25 |
ソースコード
#include <iostream>#include <vector>#include <map>#include <set>#include <queue>#include <string>#include <iomanip>#include <algorithm>#include <cmath>#include <stdio.h>using namespace std;#define int long longint MOD = 1000000007;template <typename Int, Int MOD, int N>struct comb_util {std::array<Int, N + 1> fc, ifc;comb_util() {fc[0] = 1;for (int i = 1; i <= N; i++) fc[i] = fc[i - 1] * i % MOD;ifc[N] = inv(fc[N]);for (int i = N - 1; i >= 0; i--) ifc[i] = ifc[i + 1] * (i + 1) % MOD;}Int fact(Int n) { return fc[n]; }Int inv_fact(Int n) { return ifc[n]; }Int inv(Int n) { return pow(n, MOD - 2); }Int pow(Int n, Int a) {Int res = 1, exp = n;for (; a; a /= 2) {if (a & 1) res = res * exp % MOD;exp = exp * exp % MOD;}return res;}Int perm(Int n, Int r) {if (r < 0 || n < r)return 0;elsereturn fc[n] * ifc[n - r] % MOD;}Int binom(Int n, Int r) {if (n < 0 || r < 0 || n < r) return 0;return fc[n] * ifc[r] % MOD * ifc[n - r] % MOD;}Int homo(Int n, Int r) {if (n < 0 || r < 0) return 0;return r == 0 ? 1 : binom(n + r - 1, r);}};using comb = comb_util<long long, 1000000007, 300000>;comb cb;void add(int &a, const int &b) {a += b;if (a >= MOD)a -= MOD;}signed main() {cin.tie(0);ios::sync_with_stdio(false);int N;cin >> N;vector<int> A(N), B(N);int res = 0;set<int> st;vector<int> X;map<int, int> mp;for (int i = 0; i < N; i++) {cin >> A[i] >> B[i];st.insert(A[i]);st.insert(B[i]);}for (auto s : st) {mp[s] = X.size();X.push_back(s);}int M = X.size();vector<vector<int> > C(N + 1, vector<int>(N + 1, 0));C[0][0] = 1;for (int i = 1; i <= N; i++) {int sum = 0;int b = cb.inv(i + 1);if (i % 2 == 1) {for (int j = 0; j <= i; j++) {add(C[i][j], (b * sum) % MOD);add(sum, C[i - 1][j]);}}else {for (int j = i; j >= 0; j--) {add(sum, C[i - 1][j]);add(C[i][j], (b * sum) % MOD);}}}vector<int> D(N);for (int i = 0; i < N; i++) {D[i] = 0;for (int j = 0; j <= N; j++) {add(D[i], C[i + 1][j]);}//cerr << i << " " << D[i] << endl;}vector<int> E(N);for (int i = 0; i < N; i++) {E[i] = 1;if (i > 0) {E[i] = cb.inv(D[i - 1]);}E[i] = (E[i] * D[i]) % MOD;}//cerr << (E[0] * E[1]) % MOD << endl;vector<vector<int> > dp(M - 1, vector<int>(N, 0));int l = mp[A[0]];int r = mp[B[0]];int b = cb.inv(B[0] - A[0]);for (int i = l; i < r; i++) {dp[i][0] = b * (X[i + 1] - X[i]) % MOD;}int inv2 = (MOD + 1) / 2;for (int i = 1; i < N; i++) {vector<vector<int> > ndp(M - 1, vector<int>(N, 0));l = mp[A[i]];r = mp[B[i]];b = cb.inv(B[i] - A[i]);if (i % 2 == 1) {int sum = 0;for (int j = 0; j < M - 1; j++) {if (l <= j && j < r) {int tt = ((X[j + 1] - X[j]) * b) % MOD;add(ndp[j][0], tt * sum % MOD);for (int k = 0; k < N - 1; k++) {add(ndp[j][k + 1], ((tt * dp[j][k] % MOD) * E[k]) % MOD);}}for (int k = 0; k < N; k++) {add(sum, dp[j][k]);}}}else {int sum = 0;for (int j = M - 2; j >= 0; j--) {if (l <= j && j < r) {int tt = ((X[j + 1] - X[j]) * b) % MOD;add(ndp[j][0], tt * sum % MOD);for (int k = 0; k < N - 1; k++) {add(ndp[j][k + 1], ((tt * dp[j][k] % MOD) * E[k]) % MOD);}}for (int k = 0; k < N; k++) {add(sum, dp[j][k]);}}}swap(dp, ndp);}for (int i = 0; i < M - 1; i++) {for (int j = 0; j < N; j++) {add(res, dp[i][j]);}}cout << res << endl;}