CF 1467D. Sum of Paths
littlechai
2021-01-11 20:45:31
[1467D. Sum of Paths](http://codeforces.com/contest/1467/problem/D)
#### 题意：
从数组中任意一个位置开始出发走一条长度为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步，这样就可以动态更新了。
```cpp
#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);
}
}
```