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
*/