1. Ynoi2009 - rprsvq
首先有方差 \(=\dfrac{n-1}{n^2}\sum a_i^2-\dfrac2{n^2}\sum a_ia_j\)。
还有结论：对于大小为 \(n\) 的集合 \(S\)，所有 \(\dbinom nt\) 个大小为 \(t\) 的子集中，含有给定大小为 \(k\) 的子集的集合个数为 \(\dbinom {n-k}{t-k}\)。
那么一个序列 \(a_1,...,a_n\) 的子序列的方差和就是：
\(\sum_{t=1}^n\dfrac{t-1}{t^2}\dbinom{n-1}{t-1}\sum a_i^2-2\sum_{t=1}^n\dfrac 1{t^2}\dbinom{n-2}{t-2}\sum a_ia_j\)。
即
\(\sum_{t=1}^n\dfrac{\dbinom{n-2}{t-2}}{t^2}[n\sum a_i^2-(\sum a_i)^2]\)。
右半边使用线段树维护，左半边 \(=\dfrac{2^n-1-\sum_{t=1}^n\dfrac 1t\dbinom nt}{n(n-1)}\)。那个和式是 A103213 除掉阶乘，可以递推计算。
点击查看代码
//P6108
#include <bits/stdc++.h>
using namespace std; typedef long long ll;
void solve();int main(){ solve(); return 0; }
const int N = 5e6 + 10;
const ll P = 998244353;
int n, m;
ll pw2[N], fg[N], fac[N], inv[N], vg[N];
struct node{
int sum, len, pw, tag;
} t[N*4];
ll qp(ll x, ll y){
ll ans = 1;
while(y){
if(y & 1){
ans = ans * x % P;
}
x = x * x % P;
y >>= 1;
}
return ans;
}
void build(int p, int l, int r){
t[p].len = r - l + 1;
if(l != r){
int mid = l + r >> 1;
build(p<<1, l, mid);
build(p<<1|1, mid+1, r);
}
}
void psd(int p, ll v){
t[p].tag = ((ll)t[p].tag + v) % P;
t[p].pw = ((ll)t[p].pw + 2ll * t[p].sum * v) % P;
t[p].pw = ((ll)t[p].pw + v * v % P * t[p].len) % P;
t[p].sum = ((ll)t[p].sum + t[p].len * v) % P;
}
void add(int p, int l, int r, int ql, int qr, ll v){
if(qr < l || r < ql){
return;
} else if(ql <= l && r <= qr){
psd(p, v);
} else {
int mid = l + r >> 1;
psd(p<<1, t[p].tag);
psd(p<<1|1, t[p].tag);
t[p].tag = 0;
add(p<<1, l, mid, ql, qr, v);
add(p<<1|1, mid+1, r, ql, qr, v);
t[p].sum = ((ll)t[p<<1].sum + t[p<<1|1].sum) % P;
t[p].pw = ((ll)t[p<<1].pw + t[p<<1|1].pw) % P;
}
}
pair<ll, ll> qry(int p, int l, int r, int ql, int qr){
if(qr < l || r < ql){
return make_pair(0, 0);
} else if(ql <= l && r <= qr){
return make_pair(t[p].sum, t[p].pw);
} else {
int mid = l + r >> 1;
psd(p<<1, t[p].tag);
psd(p<<1|1, t[p].tag);
t[p].tag = 0;
pair<ll, ll> x = qry(p<<1, l, mid, ql, qr);
pair<ll, ll> y = qry(p<<1|1, mid+1, r, ql, qr);
x.first = (x.first + y.first) % P;
x.second = (x.second + y.second) % P;
return x;
}
}
void solve(){
scanf("%d%d", &n, &m);
build(1, 1, n);
pw2[0] = fac[0] = 1;
fg[1] = 1, fg[2] = 5, fg[3] = 29, fg[4] = 206;
for(int i = 1; i <= n; ++ i){
pw2[i] = pw2[i-1] * 2 % P;
fac[i] = fac[i-1] * i % P;
fg[i+4] = 2ll * (i+3) * (i+2) % P * (i+2) % P * fg[i+1] % P;
fg[i+4] += (P-1) * (i+3) % P * (13+i*5) % P * fg[i+2] % P;
fg[i+4] += (13+i*4) * fg[i+3] % P;
fg[i+4] %= P;
vg[i] = qp((ll)i * (i-1) % P, P-2);
}
inv[n] = qp(fac[n], P-2);
for(int i = n-1; i >= 0; -- i){
inv[i] = inv[i+1] * (i+1) % P;
}
for(int i = 1; i <= m; ++ i){
int op, l, r;
scanf("%d%d%d", &op, &l, &r);
if(op == 1){
ll a;
scanf("%lld", &a);
add(1, 1, n, l, r, a);
} else {
auto tmp = qry(1, 1, n, l, r);
ll len = r - l + 1;
ll vx = len * tmp.second % P;
vx = (vx - tmp.first * tmp.first % P + P) % P;
ll vy = (pw2[len] - 1 - inv[len] * fg[len] % P + P + P) % P * vg[len] % P;
printf("%lld\n", vx * vy % P);
}
}
}