传送门:http://codeforces.com/contest/1467/problem/D
题意
有1到n共n个点,每个点有权值。给出一个k,你可以任选起点,然后走k步(往左或者往右),每走一步权值会累加,求所有方案数的权值和。并且给出q次对该序列的更新——点i的权值变成x,求出每次更新后该状态的答案(任选起点走k步全部方案的权值和)。
思路
k是固定的,所以我们只要预处理出每个格子被走过的次数cnt[i]即可
我们使用DP的思想,定义dp[i][j]为走了 i 步后,在点 j 的方案数
因为起点是任选的,所以对于dp[0][1~n]=1,易得dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1]
现求格子 i 被经过多少次,不妨枚举格子 i 在第 j 次经过多少次
首先经过 j 步后到达格子 i 的方案数为dp[j][i],到了格子 i 后还有k-j步可以任走
我们需要知道从格子 i 出发走k-j步的方案数,就是dp[k-j][i],因为从格子 i 走k-j步的方案数等价于走k-j步走到格子i的方案数
所以最后我们枚举 j 累加进cnt即可——cnt[i] +=dp[j][i] * dp[k-j][i],求出cnt后对于每次更新就看上一次和这一次的差值×cnt[i]即可
AC代码
#include<iostream> using namespace std; typedef long long ll; const int maxn = 5e3+5; const int mod = 1e9+7; int n,k,q,pos,x; ll a[maxn],cnt[maxn]; ll dp[maxn][maxn]; int main() { cin>>n>>k>>q; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int j=0;j<=k;j++){ for(int i=1;i<=n;i++){ if(j==0) dp[j][i]=1; else if(i==1) dp[j][i]=dp[j-1][i+1]; else if(i==n) dp[j][i]=dp[j-1][i-1]; else dp[j][i]=(dp[j-1][i-1]+dp[j-1][i+1])%mod; } } ll ans=0; for(int i=1;i<=n;i++){ for(int j=0;j<=k;j++){ cnt[i] = (cnt[i] + dp[j][i] * dp[k-j][i] % mod)%mod; } ans = (ans + a[i]*cnt[i] % mod)%mod; } while(q--){ cin>>pos>>x; if(x>a[pos]){ ans = (ans + (x-a[pos])*cnt[pos] % mod)%mod; }else{ ans = (ans - (a[pos]-x)*cnt[pos] % mod + mod + mod)%mod;//防止为负 } a[pos]=x; cout<<ans<<' '; } return 0; }