Codeforces functionality may be limited from June 18, 19:00 (UTC) to June 19, 3:00 AM (UTC) due to technical maintenance. Polygon will work as usual. ×

 
 
 
 
General
 
 
# 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
→ Source
// 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;
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details