1467D. Sum of Paths

思路：

#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);
}
}