BZOJ 4584: [Apio2016]赛艇
标签：之间 std mst AC cheng 一个 err name script
4584: [Apio2016]赛艇
Time Limit: 70 Sec Memory Limit: 256 MB
[Submit][Status][Discuss]
Description
在首尔城中，汉江横贯东西。在汉江的北岸，从西向东星星点点地分布着个划艇学校，编号依次为到。每个学校都
拥有若干艘划艇。同一所学校的所有划艇颜色相同，不同的学校的划艇颜色互不相同。颜色相同的划艇被认为是一
样的。每个学校可以选择派出一些划艇参加节日的庆典，也可以选择不派出任何划艇参加。如果编号为的学校选择
派出划艇参加庆典，那么，派出的划艇数量可以在Ai至Bi之间任意选择（Ai
校如果选择派出划艇参加庆典，那么它派出的划艇数量必须大于任意一所编号小于它的学校派出的划艇数量。输入
所有学校的Ai、Bi的值，求出参加庆典的划艇有多少种可能的情况，必须有至少一艘划艇参加庆典。两种情况不同
当且仅当有参加庆典的某种颜色的划艇数量不同
Input
第一行包括一个整数N，表示学校的数量。接下来N行，每行包括两个正整数，用来描述一所学校。其中第行包括的
两个正整数分别表示Ai,Bi（1
Output
输出一行，一个整数，表示所有可能的派出划艇的方案数除以1,000,000,007得到的余数
Sample Input
Sample Output
7
HINT
Source
题目链接
看dalao博客弄懂的 链接
1 #include 2
3 using namespace std;
4
5 const long long INF = 1000000007;
6
7 const int MAXN = 510;
8 long long n, p, top, ans;
9 long long inv[MAXN];
10 long long a[MAXN], b[MAXN], l[MAXN], r[MAXN];
11 long long h[MAXN + MAXN];
12 long long C[MAXN], g[MAXN];
13 maplong long, int> k;
14
15 template void read (tn & a) {
16 tn x = 0, f = 1; char c = getchar();
17 while (c ‘0‘ || c > ‘9‘) { if (c == ‘-‘) f = -1; c = getchar(); }
18 while (c >= ‘0‘ && c ‘9‘) { x = x * 10 + c - ‘0‘; c = getchar(); }
19 a = f == 1 ? x : -x;
20 }
21
22 void get_inv() {
23 inv[1] = 1;
24 for (int i = 2; i i) {
25 inv[i] = - ( inv[INF % i] * (INF / i) ) % INF;
26 while (inv[i] 0) inv[i] += INF;
27 }
28 }
29
30 int main() {
31 read(n);
32 get_inv();
33 for (int i = 1; i i) {
34 read(a[i]);
35 read(b[i]);
36 ++b[i];
37 h[i + i - 1] = a[i];
38 h[i + i] = b[i];
39 }
40 sort(h + 1, h + 1 + n + n);
41 top = unique(h + 1, h + n + n + 1) - h - 1;
42 for (int i = 1; i i) {
43 k[h[i]] = i;
44 }
45 for (int i = 1; i i) {
46 l[i] = k[a[i]];
47 r[i] = k[b[i]];
48 }
49 // cout 50 // for (int i = 1; i 51 // for (int i = 1; i
52 g[0] = 1;
53 for (int j = 1; j j) {
54 int L = h[j + 1] - h[j];
55 C[0] = 1;
56 // cerr
57 for (int i = 1; i i) {
58 C[i] = C[i - 1] * (L + i - 1) % INF * inv[i] % INF;
59 // cerr
60 }
61 for (int i = n; i > 0; --i) {
62 if (l[i] j) {
63 long long f = 0, m = 1, c = L;
64 for (int p = i - 1; p >= 0; --p) {
65 f = (f + c * g[p]) % INF;
66 if (l[p] = j + 1) {
67 c = C[++m];
68 }
69 }
70 g[i] = (g[i] + f) % INF;
71 }
72 }
73 }
74 for (int i = 1; i INF;
75 printf("%lld\n", ans);
76 return 0;
77 }
View Code
BZOJ 4584: [Apio2016]赛艇
标签：之间 std mst AC cheng 一个 err name script
原文地址：https://www.cnblogs.com/m-m-m/p/8972987.html
评论