shabi nityacke

· · 题解

算是给 EI 题解写注吧 qwq。。

化简方差：

\frac{1}{n}\sum(a_i-\overline a)^2 =\frac{1}{n}(\sum a_i^2-2\overline {a}\sum a_i+n\overline a^2) =(\frac{1}{n}-\frac{1}{n^2})\sum a_i^2-\frac{\sum_{i\neq j}a_ia_j}{n^2}

前面那个系数 \dfrac{1}{n}-\dfrac{1}{n^2} 由 \sum a_i 贡献 \dfrac{1}{n}，由 -2\overline {a}\sum a_i 贡献 -\dfrac{2}{n^2}，由 n\overline a^2 贡献 \dfrac{1}{n^2}。

考虑所有非空子序列。枚举长度（设 L=r-l+1）有：

\left(\sum_{k=1}^L \binom{L}{k}\frac{k}{L}(\frac{1}{k}-\frac{1}{k^2})\right)\sum a_i^2-\left(\sum_{k=1}^L \binom{L}{k}\frac{k(k-1)}{L(L-1)}\frac{1}{k^2}\right)\sum_{i\neq j}a_ia_j =\left(\sum_{k=1}^L \binom{L-1}{k-1}(\frac{1}{k}-\frac{1}{k^2})\right)\sum a_i^2-\left(\sum_{k=1}^L \binom{L-2}{k-2}\frac{1}{k^2}\right)\sum_{i\neq j}a_ia_j =\left(\sum_{k=0}^{L-1} \binom{L-1}{k}(\frac{1}{k+1}-\frac{1}{(k+1)^2})\right)\sum a_i^2-\left(\sum_{k=0}^{L-2} \binom{L-2}{k}\frac{1}{(k+2)^2}\right)\sum_{i\neq j}a_ia_j

很显然，知道这两个大的括号括起来的东西就可以了。容易知道 \sum a_i^2 和 \sum_{i\neq j}a_ia_j，其中

\sum_{i\neq j}a_ia_j=\left(\sum a_i\right)^2-\sum a_i^2

据 EI 说，这一类超几何项求和式有某类共性，但是我不知道。

先处理前一半。

A_L=\sum _k\binom{L-1}{k}\frac{1}{k+1} =\sum _k\binom{L-1}{k}\int_0^1x^kdx=\int_0^1\sum_k \binom{L-1}{k}x^kdx

再次尝试用这个办法干

B_L=\sum_k \binom{L-1}{k}\frac{1}{(k+1)^2} =\sum_k \binom{L-1}{k}\frac{1}{k+1}\int _0^1x^kdx =\sum_k \binom{L-1}{k}\int_0^1x^k\int_0^1y^kdydx =\int _0^1\int_0^1\sum_k\binom{L-1}{k}x^ky^kdydx =\int_0^1\int_0^1(xy+1)^{L-1}dydx =\int_0^1\frac{(x+1)^L-1}{Lx}dx

看起来有点抽象。

B_L=\int_0^1\frac{(x+1)^{L+1}-(x+1)}{Lx(x+1)}dx =\int_1^2\frac{u^{L+1}-u}{L(u-1)u}du=\int_1^2\frac{u^{L}-1}{L(u-1)}du =\frac{1}{L}\int_1^2\sum _{i=0}^{L-1}u^idu

这，就不抽象了吧？

B_L=\frac{1}{L}\sum_{i=1}^LA_i

接下来是后半部分。

C_L=\sum_{k=0}^{L-2} \binom{L-2}{k}\frac{1}{k+2} =\sum _k\binom{L-2}{k}\int_0^1x^{k+1}dx =\int_0^1x\sum_k\binom{L-2}{k}x^kdx C_L=\int _0^1x(x+1)^{L-2}dx =\int_0^1xd\left(\frac{(x+1)^{L-1}}{L-1}\right) =\frac{x(x+1)^{L-1}}{L-1}\bigg|_{0}^1-\int_0^1\frac{(x+1)^{L-1}}{L-1}dx =\frac{2^{L-1}}{L-1}-\frac{1}{L-1}\int_0^1(x+1)^{L-1}dx

其实后几步可以省略因为没用。

虽然接下来的部分没有新意，但是我还是愿意将过程和结果展示在这里方便直接拿走（谁愿意进行这些体力劳动呢？）

D_L=\sum_{k=0}^{L-2} \binom{L-2}{k}\frac{1}{(k+2)^2} =\sum_{k=0}^{L-2} \binom{L-2}{k}\frac{1}{(k+2)}\int _0^1x^{k+1}dx =\sum_{k=0}^{L-2} \binom{L-2}{k}\int _0^1x^{k+1}\int _0^1y^{k+1}dydx =\int _0^1\int _0^1xy\sum_{k=0}^{L-2} \binom{L-2}{k}x^ky^{k}dydx =\int _0^1\frac{1}{x}\int _0^1xy(xy+1)^{L-2}d(xy)dx =\int_0^1\frac{1}{x}\left(\int_0^xy(y+1)^{L-2}dy\right)dx =\int_0^1\frac{Lx(x+1)^{L-1}-(x+1)^L+1}{xL(L-1)}dx =\int _0^1\frac{(x+1)^{L-1}}{L-1}dx-\frac{1}{(L-1)}\int_0^1\frac{(x+1)^L-1}{Lx}dx

原式等于

(A_L-B_L)\sum a_i^2-D_L\sum_{i\neq j}a_ia_j 
// Problem: P6108 [Ynoi2009] rprsvq
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P6108
// Memory Limit: 500 MB
// Time Limit: 1500 ms
// UOB Koala
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
bool mst; 
const int maxn=5e6+5,mod=998244353;
namespace IO{
    inline char gc(){
        static const int Rlen=1<<22|1;static char buf[Rlen],*p1,*p2;
        return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++;
    }
    template<typename T>T get_integer(){
        char c;bool f=false;while(!isdigit(c=gc()))f=c=='-';T x=c^48;
        while(isdigit(c=gc()))x=((x+(x<<2))<<1)+(c^48);return f?-x:x;
    }
    inline int gi(){return get_integer<int>();}
    inline int get_s(char *s){
        int len=0;char c;while(isspace(c=gc()));
        while(s[len++]=c,!isspace(c=gc())&&c!=EOF);
        s[len]=0;return len;
    }
    template<typename T>T get_float(){
        char c;bool f=false;while(!isdigit(c=gc()))f=c=='-';T x=c^48;
        while(isdigit(c=gc()))x=(x*10)+(c^48);if(c!='.')return f?-x:x;
        T y=1.;while(isdigit(c=gc()))x+=(y/=10)*(c^48);return f?-x:x;
    }
    char obuf[(int)(4e7+7)],*oh=obuf;
    inline void prt(char c){*oh++=c;}
    inline void prt(const char *s){
        while(*s)*oh++=*s++;
    }
    template<typename T>void prt(T a){
        static char ch[23];int tl=0;
        if(a<0)*oh++='-',a=-a;
        do ch[++tl]=a%10;while(a/=10);
        while(tl)*oh++=ch[tl--]^48;
    }
    template<typename T,class ...Args>
    void prt(T a,Args...args){
        prt(a),prt(args...);
    }
    struct obuf_flusher{
        ~obuf_flusher(){fwrite(obuf,1,oh-obuf,stdout);}
    }Flusher;
}
using namespace IO;
int qp(int a,int b){
    if(b==0)return 1;
    int T=qp(a,b>>1);T=1ll*T*T%mod;
    if(b&1)return 1ll*T*a%mod;
    return T;
}
#define ls (k<<1)
#define rs (k<<1|1)
#define mid ((l+r)>>1)
int xds[maxn<<2],xds2[maxn<<2],add[maxn<<2];
int A[maxn],B[maxn],D[maxn],n,m;
void pushup(int k){
    xds[k]=(xds[ls]+xds[rs])%mod;
    xds2[k]=(xds2[ls]+xds2[rs])%mod;
}
void ADD(int k,int l,int r,int v){
    int L=r-l+1;
    int s1=(xds[k]+1ll*L*v%mod)%mod;
    int s2=(xds2[k]+2ll*xds[k]*v%mod+1ll*L*v%mod*v%mod)%mod;
    xds[k]=s1,xds2[k]=s2;
    (add[k]+=v)%=mod;
}
void pushdown(int k,int l,int r){
    if(!add[k])return ;
    ADD(ls,l,mid,add[k]);
    ADD(rs,mid+1,r,add[k]);
    add[k]=0;
}
void modify(int k,int l,int r,int x,int y,int v){
    if(x<=l&&r<=y)return ADD(k,l,r,v);
    pushdown(k,l,r);
    if(x<=mid)modify(ls,l,mid,x,y,v);
    if(mid<y)modify(rs,mid+1,r,x,y,v);
    pushup(k);
}
#define PI pair<int,int>
PI operator +(const PI &a,const PI &b){
    return {(a.first+b.first)%mod,(a.second+b.second)%mod};
}
PI query(int k,int l,int r,int x,int y){
    if(x<=l&&r<=y)return {xds[k],xds2[k]};
    PI res={0,0};
    pushdown(k,l,r);
    if(x<=mid)res=res+query(ls,l,mid,x,y);
    if(mid<y)res=res+query(rs,mid+1,r,x,y);
    return res;
}
bool med;
int fac[maxn],ifac[maxn],inv[maxn];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // cerr<<(&mst-&med)/1024.0/1024.0<<endl;
    n=gi(),m=gi();
    fac[0]=1;
    for(int i=1;i<=n;i++){
        fac[i]=1ll*fac[i-1]*i%mod;
    }
    ifac[n]=qp(fac[n],mod-2);
    for(int i=n-1;i>=0;i--)ifac[i]=1ll*(i+1)*ifac[i+1]%mod;
    for(int i=1;i<=n;i++)inv[i]=1ll*ifac[i]*fac[i-1]%mod;
    int p2=1;
    for(int i=1;i<=n;i++){
        p2=p2*2%mod;
        A[i]=1ll*(p2-1+mod)%mod*inv[i]%mod;
    }
    int S=0;
    for(int i=1;i<=n;i++){
        (S+=A[i])%=mod;
        B[i]=1ll*inv[i]*S%mod;
        D[i]=1ll*(A[i]-B[i]+mod)%mod*inv[i-1]%mod;
    }
    for(int i=1;i<=m;i++){
        int tp,x,y,v;
        tp=gi(),x=gi(),y=gi();
        if(tp==1){
            v=gi();
            modify(1,1,n,x,y,v);
        }else{
            int L=y-x+1;
            PI G=query(1,1,n,x,y);
            int s1=G.second,s2=(1ll*G.first*G.first-G.second+mod)%mod;
            int res=(1ll*(A[L]-B[L]+mod)%mod*s1%mod-1ll*D[L]*s2%mod+mod)%mod;
            prt(res,"\n");
        }
    }
    return 0;
}