题解：CF1467D Sum of Paths

William2022 · 2025-07-07 08:06:48 · 题解

CF1467D Sum of Paths

切入

操作会变更元素的值，十分麻烦，但发现每个元素的贡献次数是固定的。
这么说，对于第 i 个元素存在贡献值 c_i，代表 i 在所有路径上被经过的次数总和，这样答案总为 ans=\sum a_i\times c_i。
我们仅需算出数组 c 即可算出答案，且单点修改，甚至是区间增减都不在话下。

解法

最开始想到一个二维 DP， dp_{i,j} 表示所有长度为 i 的不同路径中，j 作为终点的总次数。
从可能到达自己的位置向自己转移，容易想出这样推：

1. dp_{0,j}=1
2. dp_{i,j}=dp_{i-1,j-1}+dp_{i-1,j+1}

然后 c_j = \sum\limits_{i=0}^{k} dp_{i,j} 就行了吗？
仔细思考，发现只有结尾的计数是对的，而 i\lt k 是时候计数不正确。
怎么可能每一个节点作为起点只有一次啊？

于是开始思考，当 j 成为长度为 k 的路径上的第 x 位有多少次。

所以 j 成为长度为 k 的路径上的第 x 位有 dp_{x,j}\times dp_{k-x,j} 次。
因此 c_j = \sum\limits_{i=0}^{k} dp_{i,j}\times dp_{k-i,j}。

程序设计

先求出答案为 \sum a_i \times c_i。
当第 i 个值从 p 改成 q 时，将答案增加 (q-p)\times c_i，并输出。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=5005,M=1e9+7;
ll n,m,q,a[N],dp[N][N];
ll contribute[N];

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);

    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)dp[0][i]=1;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++)dp[i][j]=(dp[i-1][j-1]+dp[i-1][j+1])%M;
    }
    for(int i=1;i<=n;i++)for(int j=0;j<=m;j++){
        contribute[i]+=(dp[j][i]*dp[m-j][i])%M;
        contribute[i]%=M;
    }

    ll ans=0;
    for(int i=1;i<=n;i++)(ans+=(a[i]*contribute[i])%M)%=M;

    while(q--){
        int x,y;
        cin>>x>>y;
        ans-=(a[x]*contribute[x])%M;
        ans=(ans%M+M)%M;

        a[x]=y;
        ans+=(a[x]*contribute[x])%M;
        ans%=M;
        cout<<ans<<"\n";
    }
}