CF1467D

这道题一开始用了一种错误的DP思路 T T ，错误的把除了最外面4个点以外其他点左右的情况当做了对称的（肯定不是对称的啊啊啊！！）

因为题目前两个样例都是5，非常的小，所以感觉还很对，当然后面会错。

其实离正确的思路差的不是很多，但是最妙的一步没想到。

我们以dp[i][j]表示走了i步刚好到j点的方案数，那么反过来说，从j点开始走i步的方案数也是这个。

所以说一个k步的方案中，中间第s个点是j的方案数正好就是dp[s][j]*dp[k-s][j]  （走s步到j然后再从j走k-s步）

那么我们只要事先把DP数组预处理好之后对每个点在0-k步中的出现求个和，就能获得想要的东西了。

PS：之前错误就是求出DP数组之后用的方法不对，试图用一个看起来很对的玄学办法结果当然WA了

下附代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll MOD=1e9+7;
ll n,k,q,dp[5005][5005],a[5005],b[5005];
int main(){
    scanf("%lld%lld%lld",&n,&k,&q);
    for (int i=1; i<=n; i++){
        dp[0][i]=1;
    }
    for (int i=1; i<=k; i++){
        for (int j=1; j<=n; j++){
            if (j==1) dp[i][j]=dp[i-1][j+1];
            else if (j==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++){
            b[i]=(b[i]+dp[j][i]*dp[k-j][i]%MOD)%MOD;
        }
    }
    ll sum=0;
    for (int i=1; i<=n; i++){
        scanf("%lld",&a[i]);
        sum=(sum+a[i]*b[i]%MOD)%MOD;
    }   
   /* for (int i=1; i<=n; i++)
        printf("%lld ",b[i]);
    printf("
"); */
    while (q--){
        ll x,y;
        scanf("%lld%lld",&x,&y);
        sum=((sum+b[x]*y%MOD-a[x]*b[x]%MOD)%MOD+MOD)%MOD;
        a[x]=y;
        printf("%lld
",sum);
    }
    return 0;
}