1467D. Sum of Paths

题意:

从数组中任意一个位置开始出发走一条长度为k的路径,每一步向左或向右走但不能越界。每次更改一个位置的权值,并求所有路径的和是多少。

思路:

显然每个点被经历的次数是固定的设为$cnt[i]$,设$dp[i][j]$为从i点开始长度为j的路径条数,则$dp[i][j] = dp[i-1][j-1] + dp[i+1][j-1]$,又可发现该式对于定义以i点结束且长度为j的路径条数一样适用。已知总路线长度为k,则经过i点的路径条数$cnt[i]$ $=$ $\sum\limits_{j = 0}^k dp[i][j]*dp[i][k-j]$含义为走j步走到i点,再从i点走j步,这样就可以动态更新了。

#include<bits/stdc++.h>
#define lowbit(x) ((x)&(-x)) 
#define ri register int
#define ll long long
#define lson rt << 1, l, mid
#define rson rt << 1|1, mid+1, r
using namespace std;
void re(ll &x){
    x = 0;
    int b = 0;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch == '-') b = 1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x << 1) + (x << 3) + ch - '0';
        ch = getchar();
    }
    if(b == 1)
        x *= -1;
}
const int maxn = 5100;
const int p = 1e9+7;
ll n, k, q;
ll dp[maxn][maxn], f[maxn][maxn], a[maxn], cnt[maxn];
void pre_work(){
    for(int i = 1;i <= n;i ++)
        dp[i][0] = 1;

    for(int j = 1;j <= k;j ++){
        for(int i = 1;i <= n;i ++){
            dp[i][j] += dp[i-1][j-1] + dp[i+1][j-1];
            dp[i][j] %= p;
        }
    }
    for(int i = 1;i <= n;i ++){
        for(int j = 0;j <= k;j ++){
            cnt[i] = (cnt[i] + dp[i][j]*dp[i][k-j]%p)%p;

        }
    }

}
int main(){
    re(n), re(k), re(q);
    for(int i = 1;i <= n;i ++)
        re(a[i]);
    pre_work();
    ll ans = 0;
    for(int i = 1;i <= n;i ++)
        ans = (ans + a[i]*cnt[i]%p)%p;

    for(int i = 1;i <= q;i ++){
        ll pos, x;
        re(pos), re(x);
        ans = (ans - a[pos]*cnt[pos]%p + p)%p;
        a[pos] = x;
        ans = (ans + a[pos]*cnt[pos]%p)%p;
        printf("%lld\n",ans);
    }
}