题意概述
给定 \(n\) 个区间，实数序列 \(a_i\) 在区间 \([l_i,r_i]\) 上服从均匀分布，每个元素生成相互独立，求：
\[\sum_{i=2}^{n}{\left|a_i-a_{i-1} \right|}
\]
的期望，模 \(10^9+7\)。
思路
如果两区间不交，期望为两区间中点之差的绝对值。
如果两区间完全相同，将区间分成两半，有 \(1/2\) 概率两个点不属于同一个区间，这样就是两区间不交的情况；有 \(1/2\) 概率两个点属于同一区间，那这个问题和原问题是等价的，递归计算即可。此时期望为：
\[len \cdot \sum_{i=1}^{\infty}{\frac{1}{4^i}} = \frac{len}{3}
\]
如果两区间不完全相同又有交，则可以分裂成若干区间，这些区间之间要么完全相同，要么不交，独立计算贡献即可。
但要注意，需要特判常数点。
代码中采用递归实现情况三的区间分裂，最多只会递归 \(1\) 次。
时间复杂度 \(\mathcal{O}(n)\)。
代码
//author:kzssCCC#include <bits/stdc++.h>
using namespace std;
using ll = long long;const int MOD = 1e9+7;ll qpow(ll a,ll b){ll res = 1;while (b){if (b&1){res = res*a%MOD;}a = a*a%MOD;b >>= 1;}return res;
}
void solve(){int n;cin >> n;vector<pair<int,int>> a(n+1);for (int i=1;i<=n;i++){cin >> a[i].first >> a[i].second;}ll t2 = qpow(2,MOD-2);ll t3 = qpow(3,MOD-2);function<ll(int,int,int,int)> cal = [&](int l1,int r1,int l2,int r2)->ll{if (l1>l2){swap(l1,l2);swap(r1,r2);}if (l1==r1 && l2==r2){return abs(r1-r2); }else if (l1==r1){ll p = (l2+r2)*t2%MOD;return (p-r1+MOD)%MOD;}else if (l2==r2){if (r2>=r1){ll p = (l1+r1)*t2%MOD;return (r2-p+MOD)%MOD;} else{ll p1 = (l1+r2)*t2%MOD;ll p2 = (r2+r1)*t2%MOD;ll temp = qpow(r1-l1,MOD-2);return ((r2-l1)*temp%MOD*((r2-p1+MOD)%MOD)%MOD+(r1-r2)*temp%MOD*((p2-r2+MOD)%MOD)%MOD)%MOD;}}if (r1<=l2){ll p1 = (l1+r1)*t2%MOD; ll p2 = (l2+r2)*t2%MOD;return (p2-p1+MOD)%MOD; }if (l1==l2 && r1==r2){return (r1-l1)*t3%MOD; }int l = max(l1,l2);int r = min(r1,r2);vector<pair<int,int>> left,right;if (l1!=l) left.emplace_back(l1,l);left.emplace_back(l,r);if (r!=r1) left.emplace_back(r,r1);if (l2!=l) right.emplace_back(l2,l);right.emplace_back(l,r);if (r!=r2) right.emplace_back(r,r2);ll res = 0;for (int i=0;i<left.size();i++){for (int j=0;j<right.size();j++){res = (res+(left[i].second-left[i].first)*qpow(r1-l1,MOD-2)%MOD*(right[j].second-right[j].first)%MOD*qpow(r2-l2,MOD-2)%MOD*cal(left[i].first,left[i].second,right[j].first,right[j].second)%MOD)%MOD;}}return res;};ll res = 0;for (int i=2;i<=n;i++){res = (res+cal(a[i-1].first,a[i-1].second,a[i].first,a[i].second))%MOD;}cout << res << '\n';
}int main(){ios::sync_with_stdio(false);cin.tie(0);int t;cin >> t;while (t--) solve();return 0;
}