【Codeforces 1467D】 Sum of Paths | dp、思維

隊友太強了呀…

思路一合并，啪就A了呀，很快啊！

題目大意：

定義一條好的路徑，當且僅當從任意點出發之后恰好經過了 k k k次移動，定義這條路徑的權值為經過點權值 a i a_i ai?的總和，進行 q q q次修改，每次將第 a k a_k ak?改為 x x x,詢問此時所有‘好’路徑的權值總和

題目思路：

考慮 n n n是 5000 5000 5000，所以可能要 n 2 n^2 n2預處理

如果把每個位置在多少條路徑上算出來，那么對于每次修改就比較好解決了，

所以考慮如何把每個位置在多少條路徑上計算出來

首先一個方程
d p [ i ] [ k ] = d p [ i ? 1 ] [ k ? 1 ] + d p [ i + 1 ] [ k ? 1 ] dp[i][k] = dp[i-1][k-1] + dp[i+1][k-1] dp[i][k]=dp[i?1][k?1]+dp[i+1][k?1]
這個方程的狀態為： d p [ i ] [ k ] dp[i][k] dp[i][k]表示走了 k k k步當前在i點的路徑總數

那么反過來想，這個 d p [ i ] [ k ] dp[i][k] dp[i][k]也可以表示在 i i i點還需要走 k k k步能到達任意點的路徑總數，就反過來嘛很簡單，

所以對于一個點來說，列舉他作為中間點，列舉他作為第 0 0 0步、 1 1 1步、 2 2 2步、 3 3 3步的中間點，所以對于第 i i i個點作為路徑的總數顯然是：
∑ k = 0 k = m d p [ i ] [ k ] ? d p [ i ] [ m ? k ] \sum_{k=0}^{k=m}dp[i][k] * dp[i][m-k] ∑k=0k=m?dp[i][k]?dp[i][m?k]

然后這問題就解決了…
很自信的終測沒結束就寫題解，不信還能hack掉

Code:

/*** keep hungry and calm CoolGuang!  ***/
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e17+7;
const ll maxn = 1e6+700;
const ll mod= 1e9+7;
const ll up = 1e13;
const double eps = 1e-9;
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
ll a[5005],c[5005];
ll dp[5005][5005];
int main(){
	read(n);read(m);read(p);

	for(int i=1;i<=n;i++) read(a[i]);
	for(int i=1;i<=n;i++) dp[i][0] = 1; 
	
	for(int k=1;k<=m;k++)
		for(int i=1;i<=n;i++)
			dp[i][k] = (dp[i-1][k-1] + dp[i+1][k-1])%mod;
	for(int i=1;i<=n;i++){
		for(int k=0;k<=m;k++){
			c[i] = (c[i] + (dp[i][k]*dp[i][m-k])%mod)%mod;
		}
	}
	ll ans = 0;
	for(int i=1;i<=n;i++) ans = (ans + (a[i] * c[i])%mod)%mod;
	for(int i=1;i<=p;i++){
		ll pos,x;
		read(pos);read(x);
		ans = (ans - (a[pos]*c[pos])%mod + mod)%mod;
		a[pos] = x;
		ans = (ans + (a[pos]*c[pos])%mod)%mod;
		printf("%lld\n",ans);
	}
	return 0;
}
/***
2 3
2 3 2
4 5 4 1 5
***/