专栏文章

[P6108] [Ynoi2009] rprsvq 题解

aaeiouaoeiu
P6108题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min3diya
此快照首次捕获于
2025/12/01 19:54
3 个月前
此快照最后确认于
2025/12/01 19:54
3 个月前
查看原文
拆方差式子：
1n∑i=1n(ai−aˉ)2=1n∑i=1nai2+aˉ2−2aiaˉ=(1n∑i=1nai2)+aˉ2−2aˉ2=1n∑i=1nai2−(1n∑i=1nai)2\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}
然后分成两项，分别统计子序列权值之和。
对于第一项，考虑对 aia_i 的贡献求和。
∑i=1nai2∑x=1n1x(n−1x−1)=∑i=1nai2∑x=1n(nx)n=1n(2n−1)∑i=1nai2\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}
对于第二项，先拆解：
(1n∑i=1nai)2=aˉ×1n∑i=1nai\left(\frac 1n\sum_{i=1}^na_i\right)^2=\bar a\times\frac 1n\sum_{i=1}^na_i
然后有：
∑i=1nai∑x=1n1x2sum(i,x)\begin{aligned}\sum_{i=1}^na_i\sum_{x=1}^n\frac 1{x^2}\text{sum}(i,x)\end{aligned}
其中 sum(i,x)\text{sum}(i,x) 表示包括 ii 且长度为 xx 的所有子序列的和。
sum(i,x)=ai(n−1x−1)+∑1≤y≤n,y≠iay(n−2x−2)=ai(n−2x−1)+∑y=1nay(n−2x−2)\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}
然后代入回去：
∑i=1nai∑x=1n1x2sum(i,x)=∑i=1nai∑x=1n1x2[ai(n−2x−1)+∑y=1nay(n−2x−2)]=(∑i=1nai)2∑x=1n1x2(n−2x−2)+∑i=1nai2∑x=1n1x2(n−2x−1)\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)=nn+1S(n)+2n+1−1(n+1)2∑x=1n1x2(n−2x−1)=S(n−1)G(2)=14,G(n+1)=(n−1)2n+1n(n+1)2+n−1n+1G(n)∑x=1n1x2(n−2x−2)=G(n)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)
于是线段树维护 ∑ai,∑ai2\sum a_i,\sum a_i^2 即可。
下面补充一个推导方式。
首先将 ∑x\sum_x 转成相同的形式。
∑x=1n1x2(n−1x−1)=∑x=1n1x2(n−1)!(x−1)!(n−x)!=∑x=1n(n−1)!x!x(n−x)!=1n∑x=1n(nx)x∑x=1n1x2(n−2x−2)=∑x=1n1x2(n−2)!(x−2)!(n−x)!=∑x=1n(x−1)(n−2)!x!x(n−x)!=1n(n−1)∑x=1n(nx)(x−1)x=1n(n−1)∑x=1n(nx)−(nx)x=1n(n−1)(2n−1−∑x=1n(nx)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}
接下来考虑如何求 H(n)=∑x=1n(nx)x\displaystyle H(n)=\sum_{x=1}^n\frac{\binom{n}{x}}{x}。
H(n)−H(n−1)=∑x=1n(nx)x−∑x=1n−1(n−1x)x=1n+∑x=1n−1(nx)−(n−1x)x=1n+∑x=1n−1(n−1x−1)x=1n+1n∑x=1n−1(nx)=2n−1n\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 给出的是积分做法，我不会。
codeCPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...