题解归档 - cf2228E2

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2228E2
• 本地来源：problems/cf2228E2/idea.md
• 题目链接：https://codeforces.com/contest/2228/problem/E2
• 原始标题：cf2228E2 - Amanojaku and Sequence

思路

cf2228E2 - Amanojaku and Sequence

pattern: stars and bars moments, dynamic segment summary merge.

claim: For a fixed segment, let H be the number of -1 positions and M=m-fixed_sum. If M<0, there is no valid sequence. Otherwise all weak compositions of M into H holes are symmetric, so every prefix contribution can be expressed using the first and second moments of the sum of the first h_i holes.

necessary: For position i, write the prefix as p_i+X_i, where p_i is the fixed-value prefix and X_i is the sum of allocations among the first h_i holes. We need sums of 1, X_i, and X_i^2 over all weak compositions.

sufficient: The number of compositions is C(M+H-1,H-1). By symmetry, sum X_i = ways*h_i*M/H and sum X_i^2 = ways*(h_i*M*(2M+H-1)+h_i*(h_i-1)*M*(M-1))/(H*(H+1)). Therefore each segment tree node stores enough prefix aggregates: fixed sum, hole count, sum p, sum p^2, sum p*h, sum h, and sum h*(h-1). These are closed under concatenation.

brute/check: brute.cpp processes updates and enumerates all assignments for small query M. gen.cpp generates mixed point-update/range-query tests.

edge: no holes, M=0, fixed sum larger than m, update between -1 and fixed values, all holes, single element, and ranges not aligned to tree nodes.

代码

来源：problems/cf2228E2/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=998244353;
const int maxf=1400005;
ll fac[maxf],ifac[maxf],iv[maxf];
struct node{
    int len,h;
    ll sum,sp,sq,ph,sh,hh;
};
node operator+(const node&a,const node&b){
    if(a.len==0) return b;
    if(b.len==0) return a;
    node c;
    ll as=a.sum%mod,ah=a.h%mod,bl=b.len%mod;
    c.len=a.len+b.len;
    c.h=a.h+b.h;
    c.sum=a.sum+b.sum;
    c.sp=(a.sp+b.sp+as*bl)%mod;
    c.sq=(a.sq+b.sq+2*as%mod*b.sp%mod+as*as%mod*bl)%mod;
    c.ph=(a.ph+b.ph+as*ah%mod*bl%mod+as*b.sh%mod+ah*b.sp%mod)%mod;
    c.sh=(a.sh+b.sh+ah*bl)%mod;
    c.hh=(a.hh+b.hh+2*ah%mod*b.sh%mod+bl*ah%mod*((a.h-1+mod)%mod))%mod;
    return c;
}
ll qpow(ll a,ll b){
    ll r=1;
    while(b){
        if(b&1) r=r*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return r;
}
ll C(ll n,ll k){
    if(k<0||k>n) return 0;
    return fac[n]*ifac[k]%mod*ifac[n-k]%mod;
}
node leaf(ll x){
    node c{};
    c.len=1;
    if(x==-1){
        c.h=1;
        c.sh=1;
    }else{
        ll v=x%mod;
        c.sum=x;
        c.sp=v;
        c.sq=v*v%mod;
    }
    return c;
}
struct segtree{
    int n;
    vector<ll>a;
    vector<node>tr;
    segtree(int n=0):n(n),a(n+1),tr(4*n+5){}
    void build(int id,int l,int r){
        if(l==r){
            tr[id]=leaf(a[l]);
            return;
        }
        int mid=(l+r)>>1;
        build(id<<1,l,mid);
        build(id<<1|1,mid+1,r);
        tr[id]=tr[id<<1]+tr[id<<1|1];
    }
    void upd(int id,int l,int r,int p,ll v){
        if(l==r){
            a[l]=v;
            tr[id]=leaf(v);
            return;
        }
        int mid=(l+r)>>1;
        if(p<=mid) upd(id<<1,l,mid,p,v);
        else upd(id<<1|1,mid+1,r,p,v);
        tr[id]=tr[id<<1]+tr[id<<1|1];
    }
    node qry(int id,int l,int r,int ql,int qr){
        if(ql<=l&&r<=qr) return tr[id];
        int mid=(l+r)>>1;
        if(qr<=mid) return qry(id<<1,l,mid,ql,qr);
        if(ql>mid) return qry(id<<1|1,mid+1,r,ql,qr);
        return qry(id<<1,l,mid,ql,qr)+qry(id<<1|1,mid+1,r,ql,qr);
    }
};
ll solve(node x,ll m){
    if(x.h==0){
        if(m==x.sum) return x.sq;
        return 0;
    }
    if(m<x.sum) return 0;
    ll rem=m-x.sum;
    ll ways=C(rem+x.h-1,x.h-1);
    ll M=rem%mod;
    ll ans=x.sq;
    ans=(ans+2*M%mod*iv[x.h]%mod*x.ph)%mod;
    ll c1=M*((2*M%mod+(x.h-1)%mod)%mod)%mod;
    ll c2=M*((M-1+mod)%mod)%mod;
    ll add=(c1*x.sh+c2*x.hh)%mod*iv[x.h]%mod*iv[x.h+1]%mod;
    ans=(ans+add)%mod;
    return ans*ways%mod;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int i,T,n,q,op,l,r,p;
    ll m,v;
    fac[0]=1;
    for(i=1;i<maxf;i++) fac[i]=fac[i-1]*i%mod;
    ifac[maxf-1]=qpow(fac[maxf-1],mod-2);
    for(i=maxf-2;i>=0;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
    iv[1]=1;
    for(i=2;i<maxf;i++) iv[i]=(mod-mod/i)*iv[mod%i]%mod;
    cin>>T;
    while(T--){
        cin>>n>>q;
        segtree st(n);
        for(i=1;i<=n;i++) cin>>st.a[i];
        st.build(1,1,n);
        while(q--){
            cin>>op;
            if(op==1){
                cin>>p>>v;
                st.upd(1,1,n,p,v);
            }else{
                cin>>l>>r>>m;
                cout<<solve(st.qry(1,1,n,l,r),m)<<"\n";
            }
        }
    }
    return 0;
}