[[dp]] [[树状数组]] [[数论]]
题目概述
题目链接-洛谷
题目链接-loj
这是今天练习赛上想到了一个的方法，结果只有 36 pts，悲催。
后来发现里面有一个式子就是一个组合数，可以递推求解，改了一行代码，AC。（内心嫉妒生草）
解题思路
大多数题解都是选择 dp 区间，然后看哪些在一个区间中，我的方法类似，可以说非常像，有一些步骤是类似的，但是却又有很大的不同。
我的思路是这样的，枚举当前学校，然后选择数量，记这样的情况数为，会发现
接下来我就和大多数题解走上了不一样的道路。我们再记
，其中，非常神奇的发现
（废话）。我们考虑如何更新呢？我们会发现，接着我们把两个数组合并为一个，两维变成一维。怎么变呢？我们发现，对于一个学校的操作是在一个区间内的，对于这个区间内每一个（省略掉了第一维，用树状数组维护），相当于将其加上了它之前所有数的和。此时我们只需要从枚举然后每次加上其位置之前的所有数和就行。而答案就是最后中所有数的和减去，因为是，必须有船。
但是这个区间依然是级别的，怎么办呢？我们考虑到离散化，我们记录下每一个小的区间，对于第个学校，我们依然倒着枚举其覆盖的每一个小区间。显然对于这个区间，我们要加上这个区间之前所有段的和，而难点在于维护区间内的情况。
我们手算一下发现，当最开始这个段中都为时，假设段长为对于这个段来说每一个都加上，那么和就是，这时如果又要对这个段每个都加上呢？我们会发现，之前的相当于会求一个前缀和，对于区间内部相当于会从到相当于求了个前缀和，然后再加上，并且对于每次加进来的数，我们会发现它们是相互独立的，因此我们将每次加进区间的数存进一个 vector ，然后每次又有新的数加进来时分别计算每个数新增的贡献。手算几遍我们会发现，每次会新增（包括第一次）
用手暴力算几次前缀和找个规律就能发现，我们发现对于一个每次新增的系数其实就是，这里代表这个是第几个加进来的（从开始，最新的会发现少一次，加上就行，这就是为啥上面式子第一个我要拆开的原因）。
但是当时我考试的时候直接去算的这个式子，我十分的不理解。加上我上面的那个式子，其实不用看出来是组合数都能看出每次新增的乘积了吧，递推就行，所以我是傻逼 。
来看代码，不长。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
| #include <bits/stdc++.h>
#define N 510
#define mod 1000000007ll
using namespace std;
using ll = long long;
int n;
ll a[N], b[N];
ll bian[N << 1];
int cnt;
ll tr[N << 1];
ll fact[N], inv[N];
deque <ll> jia[N << 1];
ll qp(ll x, ll y) {
ll ans = 1;
while (y) {
if (y & 1) ans = ans * x % mod;
y >>= 1;
x = x * x % mod;
}
return ans;
}
void add(int p, ll v) {
while (p <= cnt) {
tr[p] = (tr[p] + v) % mod;
p += (p & -p);
}
}
ll qur(int p) {
ll ans = 0;
while (p) {
ans += tr[p];
ans %= mod;
p -= (p & -p);
}
return ans;
}
int main() {
scanf("%d", &n);
fact[0] = 1;
for (int i = 1; i <= n; ++i) {
inv[i] = qp(i, mod - 2);
fact[i] = fact[i - 1] * inv[i] % mod;
}
for (int i = 1; i <= n; ++i) {
scanf("%lld%lld", a + i, b + i);
bian[i * 2 - 1] = a[i];
bian[i * 2] = b[i] + 1;
}
sort(bian + 1, bian + n * 2 + 1);
cnt = unique(bian + 1, bian + n * 2 + 1) - bian - 1;
for (int i = 1; i <= n; ++i) {
int x = lower_bound(bian + 1, bian + cnt + 1, a[i]) - bian;
int y = lower_bound(bian + 1, bian + cnt + 1, b[i] + 1) - bian;
for (int j = y - 1; j >= x; --j) {
ll tmp = qur(j - 1);
++tmp;
jia[j].emplace_front(tmp);
add(j, tmp);
for (int k = 0; k < jia[j].size(); ++k) {
jia[j][k] = jia[j][k] * (bian[j + 1] - bian[j] - 1 + k) % mod * inv[k + 1] % mod;
add(j, jia[j][k]);
}
}
}
printf("%lld", qur(cnt));
return 0;
}
|
注释掉的是我考试时的代码。其实改的话，哎，不预处理逆的话一行就能搞定，悲伤。
最终时间复杂度。
后记
这道题没有切掉纯属眼瞎，经过认真反思我认为我应该改善自己打草稿的格式，更加清除明了，并且下次遇到这种类似的需要仔细思考是否能递推解决。
