CF695 D. Sum of Paths（DP）
题意：给一个长度为n的区域，你可以任选起点走k步，每步可以向左或向右。同时每个点都有权值，走到点上即可加权值，问所有走的方案的权值之和，再有q次询问每次会更改一点权值，再求和。
题解：可恶的带修询问卡掉了我的记忆化搜索，不然就是个水题。有带修的话，就只能先计算出每个点经过的次数，再O（1）更新答案。
考虑dp，设dp[i] [j]，表示第j步踩在i点上的方案数，易得dp[i] [j]=dp[i] [j-1]+dp[i] [j]，主要问题是第j步踩在i点时，之后还有延续，有分枝，简单求和是一个肯定错误的答案，想了很久，一直不知道怎么处理，看完题解我只能说真的太巧了，自己也太蠢了，想不到。dp[i] [j]表示的j步后到i点，那么同时也可以视为起点为i，走j步可以走的方案数，那么dp[i] [j]的延续数不就是dp[i] [k-j]吗？解决这个问题，此问题就迎刃而解了。
#include<iostream>
using namespace std;
#define ll long long
const ll mod=1e9+7;
ll n,k,q;
ll a[20007],dp[5007][5007],cnt[5007];
void init(){
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++){
if(i==1){
dp[i][j]=dp[i+1][j-1];
}
else if(i==n){
dp[i][j]=dp[i-1][j-1];
}
else{
dp[i][j]=(dp[i-1][j-1]+dp[i+1][j-1])%mod;
}
}
}
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]%mod)%mod;
}
}
}
int main(){
scanf("%lld%lld%lld",&n,&k,&q);
init();
ll sum=0;
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
sum=(sum+cnt[i]*a[i]%mod)%mod;
}
ll p,x;
while(q--){
scanf("%lld%lld",&p,&x);
sum=(sum-a[p]*cnt[p]%mod+mod)%mod;
a[p]=x;
sum=(sum+a[p]*cnt[p]%mod)%mod;
printf("%lld\n",sum);
}
}