CC

自然万物都趋向从有序变得无序

0%

2018 暑假牛客多校牛客训练 (9) H Prefix Sum

发表于 更新于 分类于 Valine：

题目链接

Problem Description

Niuniu has learned prefix sum and he found an interesting about prefix sum.

Let’s consider (k+1) arrays a[i] (0 <= i <= k)

The index of a[i] starts from 1.

a[i] is always the prefix sum of a[i-1].

“always” means a[i] will change when a[i-1] changes.

“prefix sum” means a[i][1]=a[i−1][1]anda[i][j]=a[i][j−1]+a[i−1][j]a[i][1] = a[i-1][1] and a[i][j] = a[i][j-1] + a[i-1][j] (j >= 2)

Initially, all elements in a[0] are 0.

There are two kinds of operations, which are modify and query.

For a modify operation, two integers x, y are given, and it means a[0][x]+=y.a[0][x] += y.

For a query operation, one integer x is given, and it means querying a[k][x].a[k][x].

As the result might be very large, you should output the result mod 1000000007.

Input

The first line contains three integers, n, m, k.
n is the length of each array.
m is the number of operations.
k is the number of prefix sum.

In the following m lines, each line contains an operation.

If the first number is 0, then this is a change operation.
There will be two integers x, y after 0, which means a[0][x]+=ya[0][x] += y;
If the first number is 1, then this is a query operation.

There will be one integer x after 1, which means querying a[k][x]a[k][x].

1 <= n <= 100000
1 <= m <= 100000
1 <= k <= 40
1 <= x <= n
0 <= y < 1000000007

Output

For each query, you should output an integer, which is the result.

Sample intput

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

Sample Output

1
3
7
13
1
3
8
16

题意:

往下看

思路:

官方题解：

考虑更暴力的做法

题目总共给的时间是3e8，我们每次更新需要的时间大概是4e6，那么我们大概可以进行3e8/4e6 = 75次，我们大概总共1e5次查询，那么对于查询我们分块进行，大概分成1e5/75 块，然后暴力处理即可。

分块代码:

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
76
77
78
79
80
81
82
/*************************************************************************
    > File Name: acm.cpp
    > Author: wood
    > Mail: cbcruel@gmail.com
    > Created Time: 2018年08月20日 星期一 11时50分46秒
 ************************************************************************/

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const LL  mod = 1e9 + 7;
const int maxn = 1e5 + 50;
#define fi first
#define se second
#define mp make_pair
#define pb push_back

LL inv[maxn], fi[maxn];
LL v[42][maxn];
int n,m,k;

vector<pair<int,int> > q, qq;

LL qpow(LL x, LL n){
    LL ans = 1;
    x = x % mod;
    while(n){
        if(n&1) ans = ans * x % mod;
        x = x * x % mod;
        n >>= 1;
    }return ans;
}

void init(){
    fi[0] = 1;
    for(int i = 1; i < maxn; ++i) fi[i] = fi[i-1] * i % mod;
    inv[maxn-1]=qpow(fi[maxn-1],mod-2);//阶乘逆元
    for(int i=maxn-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
}

LL C(int n, int m){
    if(n < m) return 0;
    return fi[n] * inv[m] % mod * inv[n-m] % mod;
}

void upd(){
    for(int i = 1; i <= k; ++i)
        for(int j = 1; j <= n; ++j)
            v[i][j] = (v[i-1][j] + v[i][j-1]) % mod;
}

int main(){
    init();
    scanf("%d%d%d", &n,&m,&k);
    while(m--){
        int op,x,y;
        scanf("%d%d",&op,&x);
        if(!op){
            scanf("%d", &y);
            q.pb(mp(x,y));
        }else q.pb(mp(x,-1));
    }
    int sz = 1456;
    for(auto &x: q){
        if(x.se == -1){
            LL ans = v[k][x.fi];
            for(auto &y: qq){
                if(y.fi > x.fi) continue;
                ans += y.se * C(k + x.fi - y.fi-1, k-1) % mod;
            }printf("%lld\n",ans%mod);
        }else {
            qq.pb(x);
            if(qq.size() == sz){
                for(auto &y: qq)
                    (v[0][y.fi] += y.se) %= mod;
            qq.clear();
            upd();
            }
        }
    }return 0;
}

树状数组代码

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
/*************************************************************************
    > File Name: acm.cpp
    > Author: wood
    > Mail: cbcruel@gmail.com
    > Created Time: 2018年08月20日 星期一 11时50分46秒
 ************************************************************************/

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const LL  mod = 1e9 + 7;
const int maxn = 1e5 + 50;
#define fi first
#define se second
#define mp make_pair
#define pb push_back

int n;
inline int lowbit(int x) { return x & (-x); }
struct Bit {
    LL tree[maxn];
    void update(int p, int val) {
        while(p <= n) {
            tree[p] = (tree[p]+ val) % mod;
            p += lowbit(p);
        }
    }
    int query(int p) {
        int res = 0;
        while(p >= 1) {
            res = (res+tree[p]) % mod;
            p -= lowbit(p);
        }
        return res;
    }
} bit[42];

LL inv[maxn], fi[maxn];
LL qpow(LL x, LL n){
    LL ans = 1;
    x = x % mod;
    while(n){
        if(n&1) ans = ans * x % mod;
        x = x * x % mod;
        n >>= 1;
    }return ans;
}

void init(){
    fi[0] = 1;
    for(int i = 1; i < maxn; ++i) fi[i] = fi[i-1] * i % mod;
    inv[maxn-1]=qpow(fi[maxn-1],mod-2);//阶乘逆元
    for(int i=maxn-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
}

LL C(int n, int m){

    if(n >= 0){
        if(n >= m) return fi[n] * inv[m] % mod * inv[n-m] % mod;
        return 0;
    }n = m-n-1;
    int flag = 1;
    if(m&1) flag = -1;
    return (mod + flag* fi[n]*inv[m] % mod* inv[n-m] % mod) % mod;
}


int main(){
    int m,k;
    init();
    scanf("%d%d%d", &n,&m,&k);
    k--;
    while(m--){
        int op,x,y;
        scanf("%d%d", &op,&x);
        if(op){
            LL ans = 0;
            for(int i = 0; i <= k; ++i)
                ans += C(x,i) * bit[i].query(x) % mod;
            printf("%lld\n",ans % mod);
        }else {
            int y;
            scanf("%d", &y);
            for(int i = 0; i <= k; ++i)
                bit[i].update(x,C(k-x,k-i)*y % mod);
        }
    }
    return 0;
}