Sum of Paths CodeForces - 1467D

Sum of Paths CodeForces - 1467D
Tagscombinatorics dp math *2200

题意：

定义一条好的路径，当且仅当从任意点出发之后恰好经过了 k 次移动，定义这条路径的权值为经过点权值的总和(可重)，进行 q 次修改，每次将ak 改为 x ,询问此时所有‘好’路径的权值总和.
例如样例：

5 1 5
3 5 1 4 2
1 9
2 4
3 6
4 6
5 2

将第一位换成9就成了9 5 1 4 2 ，对应的答案就是62

题解：

dp动态规划
根据题目，我们要计算每个格子的贡献，设dp[i][j]表示走了j步当前在i点的路径总数
i点可能是从i-1来的也可能是i+1来的
状态转移：
dp[i][k] = dp[i-1][k-1] + dp[i+1][k-1]
dp[i][k]也可以理解成在i点还需要走k步才能到达任意点的路径总数（相当于反着想）
那么怎么考虑每个点的贡献？
如果当前点i走了m步，方案数是dp[i][m],因为一共走k步，所以还有k-m步要走，方案数是dp[i][m-k]，该点贡献就是∑m=0^m=k^dp[i][m] * dp[i][m-k]
对于每次修改，修改第i点的值，先减去原本第i点的贡献，再加新的贡献

代码：

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);
   return s*w;
}
const int maxn=5e3+9;
const int mod=1e9+7;
ll a[maxn],c[maxn];
ll dp[maxn][maxn];
int main()
{
    int n,k,p;
    cin>>n>>k>>p;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)dp[i][0]=1;

    for(int i=1;i<=k;i++)//步数 
    {
        for(int j=1;j<=n;j++)//当前格子 
        {
            dp[j][i]=(dp[j-1][i-1]+dp[j+1][i-1])%mod;
        }
    }
    ll sum=0;
    for(int i=1;i<=n;i++)//当前格子 
    {
        for(int j=0;j<=k;j++)
        {
            c[i]=(c[i]+(dp[i][j]*dp[i][k-j])%mod)%mod;
        }
    }
    for(int i=1;i<=n;i++)sum=(sum+(a[i]*c[i])%mod)%mod;
    for(int i=1;i<=p;i++)
    {
        ll pos,x;
        cin>>pos>>x;
        sum=((sum-(a[pos]*c[pos])%mod)%mod+mod)%mod;
        a[pos]=x;
        sum=(sum+(a[pos]*c[pos])%mod)%mod;
        printf("%lld\n",sum);
    }
    return 0;
}
/*
Input
5 1 5
3 5 1 4 2
1 9
2 4
3 6
4 6
5 2
Output
62
58
78
86
86
*/