从左到右有n个单元，编号为1,2，…，n。首先，您必须在任何单元上放置一个机器人。机器人必须精确地进行k次移动。
一步移动，机器人必须向左或向右移动一个单元格，前提是它不会超出范围。换句话说，如果机器人在单元格i中，则它必须移动到单元格i-1或单元格i + 1，只要它位于1和n之间（包括端点）即可。单元按访问顺序（包括放置机器人的单元）一起构成一条良好的路径。
每个像元i都有一个与之关联的值ai。令c0，c1，...，ck为按访问顺序排列的一条路径中的单元格顺序（c0是最初放置机器人的单元格，c1是机器人第一次移动后所在的单元格，依此类推；更正式地说，ci是机器人在我移动后所处的单元）。然后，将路径的值计算为ac0 + ac1 +⋯+ ack。
您的任务是计算所有可能的良好路径上的值之和。由于此数字可能非常大，因此请以109 + 7模输出。如果起始单元格不同或存在一个整数i∈[1，k]，则两个好的路径被认为是不同的，从而使i精确移动后的机器人当前单元格在这些路径中不同。
您必须将q个更新处理为a并每次打印更新后的总和。每次更新都会更改一个单元格的值。有关更多详细信息，请参见输入格式和样本输入输出。
#include<bits/stdc++.h> using namespace std; const int maxn=5005; const int mod=1e9+7; typedef long long ll; int n,m,q; ll a[maxn],c[maxn],f[maxn][maxn]; int main () { scanf("%d%d%d",&n,&m,&q); for (int i=1;i<=n;i++) scanf("%d",a+i); for (int i=1;i<=n;i++) f[i][0]=1; for (int k=1;k<=m;k++) for (int i=1;i<=n;i++) f[i][k]=(f[i-1][k-1]+f[i+1][k-1])%mod; for (int i=1;i<=n;i++) for (int k=0;k<=m;k++) c[i]=(c[i]+f[i][k]*f[i][m-k]%mod)%mod; ll ans=0; for (int i=1;i<=n;i++) ans+=a[i]*c[i]%mod,ans%=mod; for (int i=1;i<=q;i++) { int x,y; scanf("%d%d",&x,&y); ans-=a[x]*c[x]%mod; ans=(ans+mod)%mod; a[x]=y; ans+=a[x]*c[x]%mod; ans%=mod; printf("%lld ",ans); } }