1467D. Sum of Paths(妙用dp的含義)

傳送門

話說這個 D D D好水…

只要提前預處理每個格子被走過的次數 c n t [ i ] cnt[i] cnt[i]就好了

f [ i ] [ j ] f[i][j] f[i][j]表示走了 i i i步后在點 j j j的方案數

由于起點任選那么有 f [ 0 ] [ i ] = 1 f[0][i]=1 f[0][i]=1

轉移為 f [ i ] [ j ] = f [ i ? 1 ] [ j ? 1 ] + f [ i ? 1 ] [ j + 1 ] f[i][j]=f[i-1][j-1]+f[i-1][j+1] f[i][j]=f[i?1][j?1]+f[i?1][j+1]

那么現在考慮求 c n t [ i ] cnt[i] cnt[i],就是格子 i i i被經過多少次

不妨列舉格子 i i i在第 j j j次經過多少次,累加次數

首先 j j j步到達格子 i i i的方案數是 f [ j ] [ i ] f[j][i] f[j][i],但是到了格子 i i i后還有 k ? j k-j k?j步可以延續狀態

我們需要知道從格子 i i i走 k ? j k-j k?j步的方案數,其實就是 f [ k ? j ] [ i ] f[k-j][i] f[k?j][i]

因為從格子 i i i走 k ? j k-j k?j步的方案數等價于走 k ? j k-j k?j步到達格子 i i i

這是因為不管最初從哪個點出發走 k ? j k-j k?j步到達 i i i,路徑的逆程序就是格子 i i i走 k ? j k-j k?j步出去

所以列舉 j j j累加即可 c n t [ i ] + = f [ j ] [ i ] ? f [ k ? j ] [ i ] cnt[i]+=f[j][i]*f[k-j][i] cnt[i]+=f[j][i]?f[k?j][i]

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9+7;
const int maxn = 5009;
int n,k,f[maxn][maxn],q,a[maxn],cnt[maxn],ans;
signed main()
{
	cin >> n >> k >> q;
	for(int i=1;i<=n;i++)	cin >> a[i];
	for(int i=1;i<=n;i++)	f[0][i] = 1;
	for(int i=1;i<=k;i++)
	for(int j=1;j<=n;j++)
	{
		if( j==1 )	f[i][j] = f[i-1][j+1];
		else if( j==n )	f[i][j] = f[i-1][j-1];
		else	f[i][j] = ( f[i-1][j-1]+f[i-1][j+1] )%mod;
	}
	//從點i走x步有多少種方案 
	for(int i=1;i<=n;i++)
	for(int j=0;j<=k;j++)
		cnt[i] = ( cnt[i]+f[k-j][i]*f[j][i]%mod )%mod;
	for(int i=1;i<=n;i++)	ans = ( ans+cnt[i]*a[i]%mod )%mod;
	while( q-- )
	{
		int i,x; scanf("%lld%lld",&i,&x);
		ans = ( ans-cnt[i]*a[i]%mod )%mod;
		a[i] = x;
		ans = ( ans+cnt[i]*a[i]%mod )%mod;
		printf("%lld\n",(ans+mod)%mod);
	}
}