import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.StringTokenizer;
public class boat {
static long[][] choose = new long[501][501];
static long[] inverse = new long[505];
public static long inverse(long a, long mod) {
long[] inv = extended_gcd(a, mod);
if (inv[0] != 1) {
return 0;
}
else {
return (inv[1] + 2*mod)%mod;
}
}
public static long[] extended_gcd(long a, long b) {
//three numbers, first is gcd, second is x, third is y
if (a == 0) {
return new long[]{b, 0, 1};
}
long[] next = extended_gcd(b%a, a);
long tempX = next[1];
next[1] = next[2] - (b/a) * next[1];
next[2] = tempX;
return next;
}
public static void main(String[] args) {
InputReader in = new InputReader(System.in);
PrintWriter out = new PrintWriter(System.out);
int N = in.nextInt();
int[][] intervals = new int[N][2];
HashSet<Integer> points = new HashSet<>();
for (int i = 0; i <= 500; i++) {
choose[i][0] = 1;
for (int j = 1; j <= i; j++) {
choose[i][j] = (choose[i-1][j] + choose[i-1][j-1])%MOD;
}
}
for (int i = 1; i < inverse.length; i++) {
inverse[i] = inverse(i, MOD);
}
for (int i = 0; i < N; i++) {
intervals[i][0] = in.nextInt();
intervals[i][1] = in.nextInt();
points.add(intervals[i][0]);
points.add(intervals[i][1]+1);
}
ArrayList<Integer> pSort = new ArrayList<>(points);
ArrayList<ArrayList<Integer>> items = new ArrayList<>();
for (int i = 0; i < pSort.size(); i++) {
items.add(new ArrayList<>());
}
Collections.sort(pSort);
for (int i = 0; i < N; i++) {
boolean flag = false;
for (int j = 0; j < pSort.size(); j++) {
if (pSort.get(j) == intervals[i][1]+1) {
break;
}
if (flag || pSort.get(j) == intervals[i][0]) {
flag = true;
items.get(j).add(i+1);
}
}
}
long[] dp = new long[N+1];
dp[0] = 1;
for (int i = 0; i < pSort.size()-1; i++) {
long[] pref = new long[N+1];
pref[0] = dp[0];
for (int j = 1; j <= N; j++) {
pref[j] = dp[j] + pref[j-1];
}
ArrayList<Integer> item = items.get(i);
long[] pathCount = new long[item.size()];
long sz = pSort.get(i+1) - pSort.get(i);
long[] szCount = new long[item.size()];
szCount[0] = (sz*(sz-1))/2;
for (int j = 1; j < item.size(); j++) {
szCount[j] = szCount[j-1]*(sz - j - 1)*inverse[j+2];
}
for (int j = 1; j < item.size(); j++) {
for (int k = 0; k < j; k++) {
pathCount[j] += szCount[k] * choose[j-1][k];
}
}
pathCount[0] = sz;
for (int j = 0; j < item.size(); j++) {
for (int d = 0; d <= j; d++) {
dp[item.get(j)] += pathCount[d]*pref[item.get(j-d)-1];
}
}
}
long tot = 0;
for (int i = 1; i < dp.length; i++) {
tot += dp[i];
}
out.println(tot);
out.close();
}
static long MOD = (int)(1e9) + 7;
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public String nextLine() {
try {
return reader.readLine();
}
catch (IOException e) {
throw new RuntimeException(e);
}
}
public int nextInt() {
return Integer.parseInt(next());
}
public long nextLong() {
return Long.parseLong(next());
}
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
166 ms |
15156 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
166 ms |
15156 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
128 ms |
15144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
166 ms |
15156 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
