CF1467D Sum of Paths

切入

操作会变更元素的值，十分麻烦，但发现每个元素的贡献次数是固定的。
这么说，对于第

i

个元素存在贡献值

c_i

，代表

i

在所有路径上被经过的次数总和，这样答案总为

ans=\sum a_i\times c_i

。
我们仅需算出数组

c

即可算出答案，且单点修改，甚至是区间增减都不在话下。

解法

最开始想到一个二维 DP，

dp_{i,j}

表示所有长度为

i

的不同路径中，

j

作为终点的总次数。
从可能到达自己的位置向自己转移，容易想出这样推：

$dp_{0,j}=1$
$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$ 作为第 $x$ ，也就是终点，有 $dp_{x,j}$ 次。
$j$ 从 $x$ 位出发到第 $k$ 位，与从第 $k$ 位到第 $x$ 位是等价的，有 $dp_{k-x,j}$ 次。

所以

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

，并输出。

CPP

#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";
	}
}

题解：CF1467D Sum of Paths

文章操作

CF1467D Sum of Paths

切入

解法

程序设计

相关推荐

评论

题解：CF1467D Sum of Paths