QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#311674#1831. BruteforceCrayonIsGayWA 0ms120248kbC++147.8kb2024-01-22 17:08:532024-01-22 17:08:55

Judging History

你现在查看的是最新测评结果

  • [2024-01-22 17:08:55]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:120248kb
  • [2024-01-22 17:08:53]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define ll long long
#define ld long double
#define pii pair<ll,ll>
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
const ll N = 1e5+20;
const ll INF = (ll)1e18;
const ll MOD = 998244353;
inline ll read(){
    ll ret=0,f=1;char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-') f*=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        ret=(ret<<3)+(ret<<1)+ch-'0';
        ch=getchar();
    }
    return ret*f;
}
ll gcd(ll x,ll y){return y==0?x:gcd(y,x%y);}
ll chkpow[10][10];
ll kpow(ll a,ll b,ll mod){
    if(a<=10&&b<=10)
        if(chkpow[a][b]!=0)
            return chkpow[a][b];
    ll ret=1,base=a%mod;while(b){if(b&1) ret=ret*base%mod;base=base*base%mod;b>>=1;}
    if(a<=10&&b<=10)
        return chkpow[a][b]=ret;
    return ret;
}
inline ll upd(ll x){return (x%MOD+MOD)%MOD;}
ll C[10][10];
inline ll get_d(ll k,ll c,ll w){
    return C[k][c]*kpow(w,k-c,MOD);
}
ll n,m,k,W,a[N];
const ll V = 1e5;
struct segment_tree0{
    ll mod;
    ll cnt[N*4],sum[N*4],sum_k[6][N*4];
    ll tg[N*4];
    segment_tree0(){memset(cnt,0,sizeof(cnt));memset(sum,0,sizeof(sum));memset(sum_k,0,sizeof(sum_k));memset(tg,0,sizeof(tg));}
    inline void push_up(int rt){
        sum[rt]=sum[rt<<1]+sum[rt<<1|1];
        for(int i=0;i<=k;++i)
            sum_k[i][rt]=upd(sum_k[i][rt<<1]+sum_k[i][rt<<1|1]);
        cnt[rt]=cnt[rt<<1]+cnt[rt<<1|1];
    }
    inline void modify(int rt,ll v){
        tg[rt]+=v;
        for(int i=k;i>=0;i--)
            for(int j=i-1;j>=0;j--)
                sum_k[i][rt]=upd(sum_k[i][rt]+sum_k[j][rt]*get_d(i,j,v));
        sum[rt]=sum_k[k][rt];
    }
    inline void push_down(int rt){
        if(tg[rt]!=0){
            modify(rt<<1,tg[rt]);
            modify(rt<<1|1,tg[rt]);
            tg[rt]=0;
        }
    }
    inline ll query_sz(ll rt,ll l,ll r,ll idx){
        if(r<=idx) return cnt[rt];
        if(l>idx)  return 0;
        int mid=(l+r)>>1;
        return query_sz(rt<<1,l,mid,idx)+query_sz(rt<<1|1,mid+1,r,idx);
    }
    inline void update_v(ll rt,ll l,ll r,ll w,ll c){
        if(r<w||l>w) return;
        if(l==r){
            if(c==1){
                ll id=query_sz(1,0,V,w)+1;
                cnt[rt]++;
                // cout<<"id="<<id<<endl;
                for(ll i=0;i<=k;++i)
                    sum_k[i][rt]=upd(sum_k[i][rt]+w*kpow(id,i,mod)%mod);
            }else{
                ll id=query_sz(1,0,V,w);
                cnt[rt]--;
                for(ll i=0;i<=k;++i)
                    sum_k[i][rt]=upd(sum_k[i][rt]-w*kpow(id,i,mod)%mod);
            }
            sum[rt]=sum_k[k][rt];
            return ;
        }
        int mid=l+r>>1;
        push_down(rt);
        update_v(rt<<1,l,mid,w,c);
        update_v(rt<<1|1,mid+1,r,w,c);
        push_up(rt);
    }
    inline void update_i(ll rt,ll l,ll r,ll ql,ll qr,ll v){
        if(r<ql||l>qr) return;
        if(ql<=l&&r<=qr){
            if(v==1){
                // cout<<"l="<<l<<" r="<<r<<" ql="<<ql<<" qr="<<qr<<" ans=";
                for(int i=k;i>=0;i--)
                    for(int j=i-1;j>=0;j--)
                        sum_k[i][rt]=upd(sum_k[i][rt]+sum_k[j][rt]*get_d(i,j,v));
            }else{
                for(int i=k;i>=0;i--)
                    for(int j=i-1;j>=0;j--)
                        sum_k[i][rt]=upd(sum_k[i][rt]+sum_k[j][rt]*get_d(i,j,v));
            }
            // cout<<sum[rt]<<endl;
            sum[rt]=sum_k[k][rt];
            tg[rt]+=v;
            return ;
        }
        int mid=(l+r)>>1;
        push_down(rt);
        update_i(rt<<1,l,mid,ql,qr,v);
        update_i(rt<<1|1,mid+1,r,ql,qr,v);
        push_up(rt);
    }
}sg0;
struct segment_tree1{
    ll cnt[N*4],sum[N*4],sum_k[5][5][N*4];
    //                         bi i
    ll tg[N*4];
    segment_tree1(){memset(cnt,0,sizeof(cnt));memset(sum,0,sizeof(sum));memset(sum_k,0,sizeof(sum_k));memset(tg,0,sizeof(tg));}
    inline void push_up(int rt){
        sum[rt]=sum[rt<<1]+sum[rt<<1|1];
        for(int i=0;i<W;++i)
            for(int j=0;j<W;++j)
                sum_k[i][j][rt]=upd(sum_k[i][j][rt<<1]+sum_k[i][j][rt<<1|1]);
        cnt[rt]=cnt[rt<<1]+cnt[rt<<1|1];
    }
    inline void modify(int rt,ll v){
        v=(v%W+W)%W;
        ll ret[5][5];
        sum[rt]=0;
        for(int j=0;j<W;++j){
            for(int i=0;i<W;++i)
                ret[j][i]=sum_k[j][(i-v+W*2)%W][rt];
            for(int i=0;i<W;++i)
                sum_k[j][i][rt]=ret[j][i];
            for(int i=0;i<W;++i)
                sum[rt]=upd(sum[rt]+j*kpow(i,k,W)%W*sum_k[j][i][rt]%MOD);
        }
    }
    inline void push_down(int rt){
        if(tg[rt]!=0){
            modify(rt<<1,tg[rt]);
            modify(rt<<1|1,tg[rt]);
            tg[rt<<1]+=tg[rt];tg[rt<<1|1]+=tg[rt];
            tg[rt]=0;
        }
    }
    inline ll query_sz(ll rt,ll l,ll r,ll idx){
        if(r<=idx) return cnt[rt];
        if(l>idx)  return 0;
        int mid=(l+r)>>1;
        return query_sz(rt<<1,l,mid,idx)+query_sz(rt<<1|1,mid+1,r,idx);
    }
    inline void update_v(ll rt,ll l,ll r,ll w,ll c){
        if(r<w||l>w) return;
        if(l==r){
            if(c==1){
                ll id=query_sz(1,0,V,w)+1;
                cnt[rt]++;
                // cout<<"id="<<id<<endl;
                sum_k[w%W][id%W][rt]=upd(sum_k[w%W][id%W][rt]+1);
            }else{
                ll id=query_sz(1,0,V,w);
                cnt[rt]--;
                sum_k[w%W][id%W][rt]=upd(sum_k[w%W][id%W][rt]-1);
            }
            sum[rt]=0;
            for(int j=0;j<W;++j)
                for(int i=0;i<W;++i)
                    sum[rt]=upd(sum[rt]+j*kpow(i,k,W)%W*sum_k[j][i][rt]%MOD);
            return ;
        }
        int mid=l+r>>1;
        push_down(rt);
        update_v(rt<<1,l,mid,w,c);
        update_v(rt<<1|1,mid+1,r,w,c);
        push_up(rt);
    }
    inline void update_i(ll rt,ll l,ll r,ll ql,ll qr,ll v){
        if(r<ql||l>qr) return;
        if(ql<=l&&r<=qr){
            modify(rt,v);
            tg[rt]+=v;
            return ;
        }
        int mid=(l+r)>>1;
        push_down(rt);
        update_i(rt<<1,l,mid,ql,qr,v);
        update_i(rt<<1|1,mid+1,r,ql,qr,v);
        push_up(rt);
    }
}sg1;
void multi_test(){
    for(int i=0;i<=5;++i){
        C[i][0]=C[i][i]=1;
        for(int j=1;j<=i;++j)
            C[i][j]=C[i-1][j-1]+C[i-1][j];
    }
    n=read(),k=read(),W=read();
    sg0.mod=998244353;//sg1.mod=W;
    for(int i=1;i<=n;++i){
        a[i]=read();
        sg0.update_v(1,0,V,a[i],1);
        sg0.update_i(1,0,V,a[i]+1,V,1);
        sg1.update_v(1,0,V,a[i],1);
        sg1.update_i(1,0,V,a[i]+1,V,1);
    }
    ll q=read();
    while(q--){
        ll pos=read(),x=read();
        sg0.update_v(1,0,V,a[pos],-1);
        sg0.update_i(1,0,V,a[pos]+1,V,-1);
        sg0.update_v(1,0,V,x,1);
        sg0.update_i(1,0,V,x+1,V,1);
        // cout<<"*"<<sg0.sum[1]<<endl;
        sg1.update_v(1,0,V,a[pos],-1);
        sg1.update_i(1,0,V,a[pos]+1,V,-1);
        sg1.update_v(1,0,V,x,1);
        sg1.update_i(1,0,V,x+1,V,1);
        // cout<<"&"<<sg1.sum[1]<<endl;
        printf("%lld\n",upd(sg0.sum[1]-sg1.sum[1])*kpow(W,MOD-2,MOD)%MOD);
        a[pos]=x;
    }
    return ;
}
/*
Things to notice:
1. do not calculate useless values
2. do not use similar names
 
Things to check:
1. submit the correct file
2. time (it is log^2 or log)
3. memory
4. prove your naive thoughts 
5. long long
6. corner case like n=0,1,inf or n=m
7. fileio in some oi-contest
8. module on time 
9. the number of a same divisor in a math problem
10. multi-information and queries 
*/
signed main(){
    ll T=1;
    while(T--) multi_test();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 120248kb

input:

3 1 1
2 2 8
2
2 5
3 6

output:

36
14

result:

wrong answer 2nd numbers differ - expected: '30', found: '14'