2 、B B 君的第 二 题 （ hongkong .pas/cpp ）
【问题描述】
申生在内而亡，重耳在外而安
考虑 k + 1 个数组 a[i] (0 ≤ i ≤ k)。
为了方便起见，每个数组 a[i]长度为 n，下标从 1 开始。（直观来说就是第一维下
标从 0 开始，第二维下标从 1 开始。）
其中 a[i]时时刻刻是 a[i-1] (1 ≤ i ≤ k)的前缀和。
前缀和就是 a[i][1] = a[i-1][1]且 a[i][j] = a[i][j-1]+a[i-1][j] (j ≥ 2)。
比如 a[0] = {1, 0, 0, 0}，那么 a[1] = {1, 1, 1, 1}, a[2] = {1, 2, 3, 4}, a[3]
= {1, 3, 6, 10}
此时如果我们修改 a[0][3] += 1，得到新的 a[i]。
a[0] = {1, 0, 1, 0}, a[1] = {1, 1, 2, 2}, a[2] = {1, 2, 4, 6}, a[3] = {1,
3, 7, 13}。
你需要支持 2 个操作。
修改操作：输入 x, y，执行 a[0][x] += y。
询问操作：输入 x，返回 a[k][x]的值。
由于结果可能很大，你只需要输出询问的值对 1000000007 取模的结果。
【输入格式】
第一行三个整数 n, m, k，分别表示数组长度，操作次数，前缀和次数。
接下来 m 行，每行一个操作。
如果第一个数字是 0，接下来会有 2 个数字 x, y 表示修改，a[0][x] += y。
如果第一个数字是 1，接下来会有 1 个数字 x 表示询问 a[k][x]。
【输出格式】
对于每个询问操作，输出询问的值对 1000000007 取模的结果。
【输入样例】
4 11 3
0 1 1
0 3 1
1 1
1 2
1 3
1 4
0 3 1
1 1
1 2
1 3
1 4
【输出样例】 1
3
7
13
1
3
8
16
【数据范围】
对于 100%的数据，满足 1 ≤ n ≤ 100000, 1 ≤ m ≤ 100000, 1 ≤ k ≤ 10。
对于 100%的数据，满足 1 ≤ x ≤ n, 0 ≤ y < 1000000007。
对于 30%的数据，满足 1 ≤ n, m ≤ 1000。
对于另 40%的数据，满足 1 ≤ k ≤ 2。
数据非常有梯度。
2.1 题目大意
大概是问如何把 O(mlognk 2 ) 优化为 O(mlognk)。
为了把 O(nm) 而且常数还小的暴力卡飞，只能把 n 和 m 放到 200000了。
不过说起来 O(nm) 的暴力，有两种。
一种是修改 O(1)，询问 O(n)。
一种是修改 O(n)，询问 O(1)。
有没有可能把两种暴力结合起来，变成 O(m √ n) 之类的呢。
2.2 暴力做法
比如如果 4 次求和，有类似于如下的等式。
对于一般的情况，询问 x 回答需要的是
这就得到了一个 O(nm) 的做法了。
2.3 题目分析
其中
是没法维护的。
注意到组合恒等式，然后我们把组合数的定义推广到负数。
注意到最后是一个 的前缀和，很容易想到用树状数组维护。
一个正常题目一般是维护 i j a[0][i]，但是 i j 不利于计算。
因为 j 有 k + 1 个取值，所以我们需要 k + 1 个树状数组来维护。 预处理逆元。
 可以用O(k) 的时间推出来。
 可以用 O(k) 的时间推出来。
每次修改需要修改 k + 1 个树状数组，时间复杂度为 (k + 1)logn。
每次询问需要求 k+1 个树状数组的前缀和，时间复杂度为 (k+1)logn。
这个题就解决了。
2.4 参考资料
POJ 3468 k = 2 的情况就是区间修改，区间求和。
Luogu P4514 维的情况。
其实还出过 k = 3 和 k = 4 的情况，但是找不到了。 下面给出标程： #include <bits/stdc++.h>
using namespace std;
int n, m, k;
int v[105];
int c[105][100020];
int p = 1000000007;
void R(int i, int x, int y) {
for (; x <= n; x += x & -x) {
c[i][x] += y;
c[i][x] %= p;
}
}
int G(int i, int x) {
int re = 0;
for (; x > 0; x -= x & -x) {
re = (re + c[i][x]) % p;
}
return re;
}
int main() {
freopen("hongkong.in","r",stdin);
freopen("hongkong.out","w",stdout);
scanf("%d%d%d", &n, &m, &k);
k -= 1;
v[1] = 1;
for (int i = 2; i < 105; i++) {
v[i] = (long long)v[p % i] * (p - p / i) % p;
}
for (int i = 0; i < m; i++) {
int o, x, y;
scanf("%d", &o);
if (o == 0) {
scanf("%d%d", &x, &y);
long long u = 1;
for (int j = 0; j <= k; j++) {
R(j, x, (long long)y * u % p);
u = u * (k - x - j) % p * v[j + 1] % p;
if (u < 0) {
u += p;
}
}
} else if (o == 1) {
scanf("%d", &x);
long long u = 1, z = 0;
for (int j = 0; j <= k; j++) {
z = (z + u * G(k - j, x)) % p;
u = u * (x - j) % p * v[j + 1] % p;
}
printf("%lld\n", z);
} else {
assert(false);
}
}
return 0;
}
|
转播
