8.20T1 星图（拆贡献+dp+暴力卷积）

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141361722

http://cplusoj.com/d/senior/p/NODSX2301A

给定 nn 个实数的取值范围，求其笛卡尔树节点深度总和的期望。

场上搞了一大轮区间dp，结果大方向就错了。

拆贡献，考虑 jj 对 ii 是否有贡献。若 jj 对 ii 有贡献，则 jj 是 ii 的祖先，此时贡献为1。所以我们只需要计算 jj 是 ii 祖先的概率即可。

考虑 jj 为 ii 祖先的充要条件是什么，这点也是我考场没有想到的。如果这点想到了，很容易去往拆贡献那个方向想。

不妨令 j<ij<i ，只需满足： ∀k∈[j+1,i−1],ak<aj\forall k\in[j+1,i-1],a_k<a_j

我们对不可拆区间离散化再编号后，设 I(i,j)I(i,j) 为 ii 在 jj 区间里的概率， U(i,j)U(i,j) 为 ii 在比 jj 小区间里的概率。不存在就是0。这个是容易易处理的。

我们不妨枚举 jj 和其所在区间 tt ，然后从 jj 遍历到 ii ，我们处理一个 dp(i,x)dp(i,x) 表示一直到 ii ，有 xx 个在 tt 里，其他都低于 tt 。

转移： dp(i,x)=dp(i−1,x−1)×I(i,t)+dp(i−1,x)×U(i,t)dp(i,x)= dp(i-1,x-1)\times I(i,t)+dp(i-1,x)\times U(i,t)

此时 jj 对 ii 有贡献的概率就是 ∑xdp(i,x)x\sum_x \dfrac{dp(i,x)}{x} ，因为 jj 要在和他同层次的数里排第一。

此时复杂度 O(n4)O(n^4)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
 #define debag(...) fprintf(stderr, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
 #define debag(...) void(0)
#endif
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
#define mo 998244353
#define N 410
int pw(int a, int b) {
	int ans = 1; 
	while(b) {
		if(b & 1) ans *= a; 
		a *= a; b >>= 1; 
		ans %= mo; a %= mo; 
	}
	return ans; 
}
int pw(int a) { return pw(a, mo - 2); }
int fac[N], inv[N], ifac[N]; 
void init(int n) {
	int i; 
	for(i = fac[0] = 1; i <= n; ++i) fac[i] = fac[i-1] * i % mo; 
	ifac[n] = pw(fac[n], mo-2); 
	for(i = n - 1; i >= 0; --i) ifac[i] = ifac[i+1] * (i+1) % mo; 
    for(i = 1; i <= n; ++i) inv[i] = ifac[i] * fac[i-1] % mo; 
}
inline void Mod(int &a) { if(a >= mo || a <= -mo) a %= mo; if(a < 0) a += mo; }
inline void Add(int &a, int b) { a += b; Mod(a); }
inline void Mul(int &a, int b) { Mod(b); a *= b; Mod(a); } 
int n, m, i, j, k, T;
int l[N], r[N], R[N << 1], L[N << 1], v[N << 1], ans, a[N], b[N], len[N << 1], Len[N], iLen[N]; 
int Lx[N], Rx[N], In[N][N << 1], Und[N][N << 1]; 
int f[N][N << 1], t; 

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	srand(time(NULL));
//	T=read();
//	while(T--) {
//
//	}
	n = read(); init(n); 
	for(i = 1; i <= n; ++i) L[i] = Lx[i] = read(), R[i] = Rx[i] = read(); 
	for(i = 1; i <= n; ++i) Len[i] = R[i] - L[i], iLen[i] = pw(Len[i]); 
	for(i = 1; i <= n; ++i) v[++k] = L[i], v[++k] = R[i]; 
	sort(v + 1, v + 2 * n + 1); reverse(v + 1, v + 2 * n + 1); 
	for(i = 2; i <= 2 * n; ++i){
		if(v[i] != v[i - 1]) l[++m] = v[i], r[m] = v[i - 1], len[m] = r[m] - l[m]; 
	}
	for(i = 1; i <= m; ++i) debug("[%lld %lld] %lld\n", l[i], r[i], len[i]); 
	for(i = 1; i <= n; ++i) {
		int mn = 1e9, mx = 0; 
		for(j = 1; j <= m; ++j) 
			if(L[i] <= l[j] && R[i] >= r[j]) 
				mn = min(mn, j), mx = max(mx, j); 
		L[i] = mn; R[i] = mx; 
		debug("(%lld %lld) %lld %lld\n", L[i], R[i], Len[i], iLen[i]);
	}
	for(i = 1; i <= n; ++i) 
		for(j = 1; j <= m; ++j) {
			if(j < L[i]) In[i][j] = 0, Und[i][j] = 1; 
			else if(j > R[i]) In[i][j] = Und[i][j] = 0; 
			else {
				In[i][j] = len[j] * iLen[i] % mo; 
				Und[i][j] = (l[j] - Lx[i]) * iLen[i] % mo; 
			}
		}
	for(t = 1; t <= m; ++t) 
		for(k = 1; k <= n; ++k) {
			if(!In[k][t]) continue; 
			memset(f, 0, sizeof(f)); 
			f[k][1] = In[k][t] % mo; 
			debug("# %lld : %lld\n", k, f[k][1]); 
			auto work = [&] (int o) -> void {
				for(i = k + o; i <= n && i >= 1; i += o) {
					int P = 0; 
					for(j = 1; j <= abs(k - i) + 1; ++j) {
						Add(f[i][j + 1], f[i - o][j] * In[i][t]); 
						Add(f[i][j], f[i - o][j] * Und[i][t]); 
						Add(P, f[i][j] * inv[j]); 
					}
					debug("## %lld -> %lld %lld(%lld %lld %lld)\n", k, i, P, pw(2), 2 * pw(9), 2 * pw(3) % mo); 
					Add(ans, P); 
				}
			}; 
			work(1); work(-1); 
		}
	printf("%lld", ans); 
	return 0;
}



考虑继续优化，若 tt 定，我们发现 kk 对 ii 的贡献可以表达成下面的形式：

F(x)=I(k)x∏j=k+1i(U(j)+In(i)x)F(x)=I(k)x\prod_{j=k+1}^i (U(j)+In(i)x)

Ansk→i=∑k=1∣i−j+1∣[xk]F(x)kAns_{k\to i}=\sum_{k=1}^{|i-j+1|} \dfrac{[x^k]F(x)}k

发现上面就是个卷积形式，我们直接暴力维护即可。

复杂度 O(n3)O(n^3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
 #define debag(...) fprintf(stderr, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
 #define debag(...) void(0)
#endif
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
#define mo 998244353
#define N 810
int pw(int a, int b) {
	int ans = 1; 
	while(b) {
		if(b & 1) ans *= a; 
		a *= a; b >>= 1; 
		ans %= mo; a %= mo; 
	}
	return ans; 
}
int pw(int a) { return pw(a, mo - 2); }
int fac[N], inv[N], ifac[N]; 
void init(int n) {
	int i; 
	for(i = fac[0] = 1; i <= n; ++i) fac[i] = fac[i-1] * i % mo; 
	ifac[n] = pw(fac[n], mo-2); 
	for(i = n - 1; i >= 0; --i) ifac[i] = ifac[i+1] * (i+1) % mo; 
    for(i = 1; i <= n; ++i) inv[i] = ifac[i] * fac[i-1] % mo; 
}
inline void Mod(int &a) { if(a >= mo || a <= -mo) a %= mo; if(a < 0) a += mo; }
inline void Add(int &a, int b) { a += b; Mod(a); }
inline void Mul(int &a, int b) { Mod(b); a *= b; Mod(a); } 
int n, m, i, j, k, T;
int l[N], r[N], R[N << 1], L[N << 1], v[N << 1], ans, a[N], b[N], len[N << 1], Len[N], iLen[N]; 
int Lx[N], Rx[N], In[N][N << 1], Und[N][N << 1]; 
int f[N][N << 1], t, cnt, F[N << 1]; 

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	srand(time(NULL));
//	T=read();
//	while(T--) {
//
//	}
	n = read(); init(n); 
	for(i = 1; i <= n; ++i) L[i] = Lx[i] = read(), R[i] = Rx[i] = read(); 
	for(i = 1; i <= n; ++i) Len[i] = R[i] - L[i], iLen[i] = pw(Len[i]); 
	for(i = 1; i <= n; ++i) v[++k] = L[i], v[++k] = R[i]; 
	sort(v + 1, v + 2 * n + 1); reverse(v + 1, v + 2 * n + 1); 
	for(i = 2; i <= 2 * n; ++i){
		if(v[i] != v[i - 1]) l[++m] = v[i], r[m] = v[i - 1], len[m] = r[m] - l[m]; 
	}
	for(i = 1; i <= m; ++i) debug("[%lld %lld] %lld\n", l[i], r[i], len[i]); 
	for(i = 1; i <= n; ++i) {
		int mn = 1e9, mx = 0; 
		for(j = 1; j <= m; ++j) 
			if(L[i] <= l[j] && R[i] >= r[j]) 
				mn = min(mn, j), mx = max(mx, j); 
		L[i] = mn; R[i] = mx; 
		debug("(%lld %lld) %lld %lld\n", L[i], R[i], Len[i], iLen[i]);
	}
	for(i = 1; i <= n; ++i) 
		for(j = 1; j <= m; ++j) {
			if(j < L[i]) In[i][j] = 0, Und[i][j] = 1; 
			else if(j > R[i]) In[i][j] = Und[i][j] = 0; 
			else {
				In[i][j] = len[j] * iLen[i] % mo; 
				Und[i][j] = (l[j] - Lx[i]) * iLen[i] % mo; 
			}
		}
	for(t = 1; t <= m; ++t) {
		auto work = [&] (int st, int o) -> void {
			for(i = st, cnt = 0; i <= n && i >= 1; i += o, ++cnt) {
				for(j = 0; /*i != st &&*/ j <= cnt; ++j) {
					Add(ans, In[i][t] * F[j] % mo * inv[j + 1] % mo); 
					debug("%lld (%lld %lld)\n", In[i][t] * F[j] % mo * inv[j + 1] % mo, pw(2), 5 * pw(6)); 
				}
				for(j = cnt; j >= 0; --j) 
					Add(F[j + 1], F[j] * In[i][t]), Mul(F[j], Und[i][t]); 
				Add(F[0], Und[i][t]); Add(F[1], In[i][t]); 
//					Add(F[j + 1], (F[j] + 1) * In[i][t]), F[j] = (F[j] + 1) * Und[i][t] % mo; 
				debug("%lld : ", i); for(j = cnt + 1; j >= 0; --j) debug("%lld ", F[j]); debug("\n"); 
			}
		}; 
		memset(F, 0, sizeof(F)); F[0] = 0; work(n, -1); 
		memset(F, 0, sizeof(F)); F[0] = 0; work(1, 1); 
	}
	printf("%lld", ans); 
	return 0;
}