[P6108] [Ynoi2009] rprsvq 题解

· · 题解

拆方差式子：

\begin{aligned}&\frac{1}{n}\sum_{i=1}^{n}(a_i-\bar{a})^2\\&=\frac 1n\sum_{i=1}^na_i^2+\bar a^2-2a_i\bar a\\&=\left(\frac 1n\sum_{i=1}^na_i^2\right)+\bar a^2-2\bar a^2\\&=\frac 1n\sum_{i=1}^na_i^2-\left(\frac 1n\sum_{i=1}^na_i\right)^2\end{aligned}

然后分成两项，分别统计子序列权值之和。

对于第一项，考虑对 a_i 的贡献求和。

\begin{aligned}&\sum_{i=1}^na_i^2\sum_{x=1}^n\frac 1x\binom{n-1}{x-1}\\&=\sum_{i=1}^na_i^2\sum_{x=1}^n\frac{\binom{n}{x}}{n}\\&=\frac 1n(2^n-1)\sum_{i=1}^n a_i^2\end{aligned}

对于第二项，先拆解：

\left(\frac 1n\sum_{i=1}^na_i\right)^2=\bar a\times\frac 1n\sum_{i=1}^na_i

然后有：

\begin{aligned}\sum_{i=1}^na_i\sum_{x=1}^n\frac 1{x^2}\text{sum}(i,x)\end{aligned}

其中 \text{sum}(i,x) 表示包括 i 且长度为 x 的所有子序列的和。

\begin{aligned}&\text{sum}(i,x)\\&=a_i\binom{n-1}{x-1}+\sum_{1\le y\le n,y\neq i}a_y\binom{n-2}{x-2}\\&=a_i\binom{n-2}{x-1}+\sum_{y=1}^na_y\binom{n-2}{x-2}\end{aligned}

然后代入回去：

\begin{aligned}&\sum_{i=1}^na_i\sum_{x=1}^n\frac 1{x^2}\text{sum}(i,x)\\&=\sum_{i=1}^na_i\sum_{x=1}^n\frac 1{x^2}\left[a_i\binom{n-2}{x-1}+\sum_{y=1}^na_y\binom{n-2}{x-2}\right]\\&=\left(\sum_{i=1}^na_i\right)^2\sum_{x=1}^n\frac 1{x^2}\binom{n-2}{x-2}+\sum_{i=1}^na_i^2\sum_{x=1}^n\frac{1}{x^2}\binom{n-2}{x-1}\end{aligned}

然后不会了。

由 deepseek 得：

S(1)=1,S(n+1)=\frac n{n+1}S(n)+\frac{2^{n+1}-1}{(n+1)^2}\\\sum_{x=1}^n\frac{1}{x^2}\binom{n-2}{x-1}=S(n-1)\\G(2)=\frac 14,G(n+1) = \frac{(n-1)2^n+1}{n(n+1)^2} + \frac{n-1}{n+1} G(n)\\\sum_{x=1}^n\frac 1{x^2}\binom{n-2}{x-2}=G(n)

于是线段树维护 \sum a_i,\sum a_i^2 即可。

下面补充一个推导方式。

首先将 \sum_x 转成相同的形式。

\begin{aligned}&\sum_{x=1}^n\frac 1{x^2}\binom{n-1}{x-1}\\&=\sum_{x=1}^n\frac 1{x^2}\frac{(n-1)!}{(x-1)!(n-x)!}\\&=\sum_{x=1}^n\frac{(n-1)!}{x!x(n-x)!}\\&=\frac 1n\sum_{x=1}^n\frac{\binom{n}{x}}{x}\\&\sum_{x=1}^n\frac 1{x^2}\binom{n-2}{x-2}\\&=\sum_{x=1}^n\frac 1{x^2}\frac{(n-2)!}{(x-2)!(n-x)!}\\&=\sum_{x=1}^n\frac{(x-1)(n-2)!}{x!x(n-x)!}\\&=\frac1{n(n-1)}\sum_{x=1}^n\frac{\binom{n}{x}(x-1)}{x}\\&=\frac1{n(n-1)}\sum_{x=1}^n\binom{n}{x}-\frac{\binom{n}{x}}{x}\\&=\frac1{n(n-1)}\left(2^n-1-\sum_{x=1}^n\frac{\binom{n}{x}}{x}\right)\end{aligned}

接下来考虑如何求 \displaystyle H(n)=\sum_{x=1}^n\frac{\binom{n}{x}}{x}。

\begin{aligned}&H(n)-H(n-1)\\&=\sum_{x=1}^n\frac{\binom{n}{x}}{x}-\sum_{x=1}^{n-1}\frac{\binom{n-1}{x}}{x}\\&=\frac1n+\sum_{x=1}^{n-1}\frac{\binom{n}{x}-\binom{n-1}{x}}{x}\\&=\frac1n+\sum_{x=1}^{n-1}\frac{\binom{n-1}{x-1}}{x}\\&=\frac1n+\frac1n\sum_{x=1}^{n-1}\binom{n}{x}\\&=\frac{2^n-1}{n}\end{aligned}

然后就可以直接递推了。deepseek 给出的是积分做法，我不会。

::::info[code]

#include<bits/stdc++.h>
#define pb emplace_back
#define mp make_pair
#define pob pop_back
using namespace std;
typedef long long ll;
const ll maxn=5000007,ee=1e18,p=998244353;
ll n,m;
int S[maxn],G[maxn],pw[maxn],inv[maxn];
void ups(ll &a,ll b){a=(a+b>=p)?(a+b-p):(a+b);}
void ups(int &a,int b){a=(a+b>=p)?(a+b-p):(a+b);}
ll qpow(ll a,ll b){ll E=1; for(;b;b>>=1,a=a*a%p)if(b&1) E=E*a%p; return E;}
void init(void){
    pw[0]=inv[1]=1;
    for(ll i=1;i<=n+5;i++){
        pw[i]=pw[i-1]*2%p;
        if(i!=1) inv[i]=(p-1ll*(p/i)*inv[p%i]%p)%p;
    }
    S[0]=S[1]=1;
    for(ll i=1;i<n;i++) S[i+1]=(1ll*i*inv[i+1]%p*S[i]%p+(pw[i+1]-1+p)%p*inv[i+1]%p*inv[i+1]%p)%p;
    G[2]=qpow(4,p-2);
    for(ll i=1;i<n;i++) G[i+1]=(1ll*(i-1)*inv[i+1]%p*G[i]%p+((i-1)*pw[i]%p+1)*inv[i]%p*inv[i+1]%p*inv[i+1]%p)%p;
}
struct Tree{
    int s1[maxn<<2],s2[maxn<<2],add[maxn<<2];
    void pushup(ll rt){
        ups(s1[rt]=s1[rt<<1],s1[rt<<1|1]);
        ups(s2[rt]=s2[rt<<1],s2[rt<<1|1]);
    }
    void pushdown(ll rt,ll siz){
        if(!add[rt]) return;
        ll ls=siz-(siz>>1),rs=siz>>1;
        ups(s2[rt<<1],(1ll*2*s1[rt<<1]+ls*add[rt]%p)*add[rt]%p);
        ups(s2[rt<<1|1],(1ll*2*s1[rt<<1|1]+rs*add[rt]%p)*add[rt]%p);
        ups(s1[rt<<1],1ll*ls*add[rt]%p),ups(s1[rt<<1|1],1ll*rs*add[rt]%p);
        ups(add[rt<<1],add[rt]),ups(add[rt<<1|1],add[rt]),add[rt]=0;
    }
    void upd(ll l,ll r,ll x,ll y,ll d,ll rt){
        if(x<=l&&r<=y){
            ups(s2[rt],(1ll*2*s1[rt]+(r-l+1)*d)%p*d%p);
            ups(s1[rt],1ll*(r-l+1)*d%p);
            ups(add[rt],d);
            return;
        }
        pushdown(rt,r-l+1); ll mid=(l+r)>>1;
        if(x<=mid) upd(l,mid,x,y,d,rt<<1);
        if(mid<y) upd(mid+1,r,x,y,d,rt<<1|1);
        pushup(rt);
    }
    void qry(ll l,ll r,ll x,ll y,ll &r1,ll &r2,ll rt){
        if(x<=l&&r<=y) return ups(r1,s1[rt]),ups(r2,s2[rt]),void();
        pushdown(rt,r-l+1); ll mid=(l+r)>>1;
        if(x<=mid) qry(l,mid,x,y,r1,r2,rt<<1);
        if(mid<y) qry(mid+1,r,x,y,r1,r2,rt<<1|1);
    }
}tree;
int main(void){
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m;
    init();
    for(ll i=1,op,l,r,x,p2,s1,s2;i<=m;i++){
        cin>>op>>l>>r;
        if(op==1){
            cin>>x;
            tree.upd(1,n,l,r,x,1);
        }else{
            s1=s2=0,p2=(pw[r-l+1]-1+p)%p*qpow(r-l+1,p-2)%p;
            tree.qry(1,n,l,r,s1,s2,1);
            cout<<(s2*p2%p-s1*s1%p*G[r-l+1]%p+p-s2*S[r-l]%p+p)%p<<"\n";
        }
    }
    return 0;
}

::::