UPCOJ-8018-hongkong

时间限制: 1 Sec 内存限制: 128 MB

题目描述

申生在内而亡，重耳在外而安。
考虑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≤10000,1≤m≤10000,1≤k≤100。
对于100%的数据，满足1≤x≤n,0≤y<1000000007。
对于70%的数据，满足1≤k≤10。
对于30%的数据，满足1≤k≤2。

来源/分类

江苏2018省队

题解

假设题目中的a数组的第0行的值分别是a,b,c,d,e…
写一写a数组的递推过程：

列\行	1	2	3	4	5
0	a	b	c	d	e
1	a	a+b	a+b+c	a+b+c+d	a+b+c+d+e
2	a	2a+b	3a+2b+c	4a+3b+2c+d	5a+4b+3c+2d+e
3	a	3a+b	6a+3b+c	10a+6b+3c+d	15a+10b+6c+3d+e
观察它们的系数的变化，可以发现系数都来源于一个前缀和数组：

列\行	1	2	3	4	5
0	1	0	0	0	0
1	1	1	1	1	1
2	1	2	3	4	5
3	1	3	6	10	15
令这个数组为b，其递推求法为：

b[0][1]=1;
for (int i=1;i<=k;i++){
    for (int j=1;j<=n;j++){
        b[i][j]=b[i][j-1]+b[i-1][j];
    }
}

这时我们很容易就能求出a[k][x]：
a[k][x] = sum ( a[0][j]*b[k][x-j+1] ) , (1<=j<=x)

代码

#include <cstdio>

using namespace std;
typedef  long long ll;
const ll mod =1000000007;

ll n,m,k;
ll a[10050];
ll b[105][10050];

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif

    scanf("%lld%lld%lld",&n,&m,&k);
    b[0][1]=1;
    for (int i=1;i<=k;i++){
        for (int j=1;j<=n;j++){
            b[i][j]=(b[i][j-1]+b[i-1][j])%mod;
        }
    }
    while (m--){
        ll op ;
        scanf("%lld",&op);
        if (op==0){
            ll x,y;
            scanf("%lld%lld",&x,&y);
            a[x]+=y;
        }else{
            ll x;
            scanf("%lld",&x);
            ll ans = 0;
            for (ll i=1;i<=x;i++){
                ans = (ans+a[i]*b[k][x-i+1])%mod;
            }
            printf("%lld\n",ans);
        }
    }
    
    return 0;
}

/**************************************************************
    Problem: 8018
    User: WC011
    Language: C++
    Result: 正确
    Time:672 ms
    Memory:9492 kb
****************************************************************/