?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
229979788 |
Practice: racccccoon |
1467D - 16 | C++14 (GCC 6-32) | Accepted | 982 ms | 294816 KB | 2023-10-27 11:32:14 | 2023-10-27 11:32:14 |
// LUOGU_RID: 131850599 #include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=5010,mod=1e9+7; int n,k,q,a[N]; int f[N][N],g[N][N],sum[N]; int tot[N],h[N][N]; int get(int i,int j) { if(j<1||j>n)return 0; if(j==1||j==n)return g[i][j]; return (g[i][j]+1)>>1; } void init() { for(int j=1;j<=n;j++) f[0][j]=1; for(int i=1;i<=k;i++) { for(int j=1;j<=n;j++) { f[i][j]=(f[i-1][j-1]+f[i-1][j+1])%mod; } } // puts("--------------------"); // for(int i=0;i<=k;i++) // {for(int j=1;j<=n;j++)printf("%d ",f[i][j]);puts("");} // for(int j=1;j<=n;j++) // g[k][j]=f[k][j]; // for(int i=k-1;i>=0;i--) // { // for(int j=1;j<=n;j++) // { // if(j==1) // { // g[i][j]=g[i+1][j+1]>>1; // } // else if(j==n) // { // g[i][j]=g[i+1][j-1]>>1; // } // else // { // int res1=get(i+1,j-1),res2=get(i+1,j+1); // g[i][j]=(res1+res2)%mod; // // printf("%d %d %d %d\n",i,j,res1,res2); // } // } // } // puts("--------------------"); // for(int i=0;i<=k;i++) // {for(int j=1;j<=n;j++)printf("%d ",g[i][j]);puts("");} // for(int i=0;i<=k;i++) // { // for(int j=1;j<=n;j++) // { // sum[j]=(sum[j]+g[i][j])%mod; // } // } // for(int i=1;i<=n;i++) // { // printf("sum[%d]=%d\n",i,sum[i]); // } for(int j=1;j<=n;j++) { for(int i=0;i<=k;i++) { h[i][j]=1ll*f[i][j]*f[k-i][j]%mod; } } // puts("--------------------"); // for(int i=0;i<=k;i++) // {for(int j=1;j<=n;j++)printf("%d ",h[i][j]);puts("");} for(int j=1;j<=n;j++) { for(int i=0;i<=k;i++) { tot[j]=(tot[j]+h[i][j])%mod; } } // for(int i=1;i<=n;i++) // { // printf("tot[%d]=%d\n",i,tot[i]); // } } LL ans[N];int cnt; #define sum tot signed main() { scanf("%d%d%d",&n,&k,&q); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } init(); LL now=0; for(int i=1;i<=n;i++) { now=(now+1ll*sum[i]*a[i]%mod)%mod; } for(int i=1;i<=q;i++) { int x,y;scanf("%d%d",&x,&y); now = (now+(1ll*(y-a[x])*sum[x]%mod))%mod; now = (now+mod)%mod; a[x]=y; ans[++cnt]=now; } for(int i=1;i<=q;i++) printf("%lld\n",ans[i]); return 0; }
?
?
?
?