[Problem Discription] \color{blue}{\texttt{[Problem Discription]}} [Problem Discription]
定义一个数组 a 1 … n a_{1 \dots n} a1…n 的价值为 val ( a ) = ∑ i = 2 n ∣ a i − a i − 1 ∣ \text{val}(a)=\sum\limits_{i=2}^{n} \left | a_{i}-a_{i-1} \right | val(a)=i=2∑n∣ai−ai−1∣。
已知 a i ∈ [ l i , r i ] a_{i} \in \left [ l_{i},r_{i} \right ] ai∈[li,ri]，且 a i a_{i} ai 等可能的取 [ l i , r i ] [l_{i},r_{i}] [li,ri] 中的任何一个值。求 val(a) \text{val(a)} val(a) 的期望，即 E ( val ( a ) ) E(\text{val}(a)) E(val(a))。答案对 ( 1 × 1 0 9 + 7 ) (1 \times 10^{9}+7) (1×109+7) 取模。
1 ≤ n ≤ 2 × 1 0 5 , 1 ≤ l i ≤ r i ≤ 1 × 1 0 9 1\leq n \leq 2 \times 10^{5}, 1\leq l_{i} \leq r_{i} \leq 1 \times 10^{9} 1≤n≤2×105,1≤li≤ri≤1×109。
[Analysis] \color{blue}{\texttt{[Analysis]}} [Analysis]
考虑 dp。
记 f i , v f_{i,v} fi,v 表示只考虑 a 1 … i a_{1 \dots i} a1…i，且 a i = v a_{i}=v ai=v 时的期望。记 g i g_{i} gi 为只考虑 a 1 … i a_{1 \dots i} a1…i 而 a i a_{i} ai 随机取值的期望。则所求为 g n g_{n} gn
由于 a i a_{i} ai 在 [ l i , r i ] [l_{i},r_{i}] [li,ri] 中等可能取值，有：
g i = ∑ v = l i r i f i , v r i − l i + 1 g_{i}=\dfrac{\sum\limits_{v=l_{i}}^{r_{i}}f_{i,v}}{r_{i}-l_{i}+1} gi=ri−li+1v=li∑rifi,v
现在考虑 f i , v f_{i,v} fi,v 的转移方程。稍加分析可得：
f i , v = ∑ j = l i − 1 r i − 1 ( f i − 1 , j + ∣ v − j ∣ ) r i − 1 − l i − 1 + 1 f_{i,v}=\dfrac{\sum\limits_{j=l_{i-1}}^{r_{i-1}} \left ( f_{i-1,j}+\left | v-j \right | \right )}{r_{i-1}-l_{i-1}+1} fi,v=ri−1−li−1+1j=li−1∑ri−1(fi−1,j+∣v−j∣)
因此：
g i = ∑ v = l i r i f i , v r i − l i + 1 = ∑ v = l i r i ( ∑ j = l i − 1 r i − 1 ( f i − 1 , j + ∣ v − j ∣ ) r i − 1 − l i − 1 + 1 ) r i − l i + 1 g_{i}=\dfrac{\sum\limits_{v=l_{i}}^{r_{i}}f_{i,v}}{r_{i}-l_{i}+1}=\dfrac{\sum\limits_{v=l_{i}}^{r_{i}} \left ( \dfrac{\sum\limits_{j=l_{i-1}}^{r_{i-1}} \left ( f_{i-1,j}+\left | v-j \right | \right )}{r_{i-1}-l_{i-1}+1} \right )}{r_{i}-l_{i}+1} gi=ri−li+1v=li∑rifi,v=ri−li+1v=li∑ri ri−1−li−1+1j=li−1∑ri−1(fi−1,j+∣v−j∣)
这样直接转移是 O ( n × ( max i = 1 n ( r i − l i ) ) 2 ) O\left (n\times \left ( \max\limits^{n}_{i=1}(r_{i}-l_{i}) \right )^{2} \right ) O(n×(i=1maxn(ri−li))2) 的，必超时无疑。考虑优化。
展开式子：
g i = ∑ v = l i r i ( ∑ j = l i − 1 r i − 1 f i − 1 , j ) + ∑ v = l i r i ∑ j = l i − 1 r i − 1 ∣ v − j ∣ ( r i − l i + 1 ) ( r i − 1 − l i − 1 + 1 ) g_{i}=\dfrac{\color{red}{\sum\limits_{v=l_{i}}^{r_{i}}\left ( \sum\limits_{j=l_{i-1}}^{r_{i-1}}f_{i-1,j} \right )} \color{black}{+}\color{blue}{\sum\limits_{v=l_{i}}^{r_{i}}\sum\limits_{j=l_{i-1}}^{r_{i-1}}|v-j|}}{(r_{i}-l_{i}+1)(r_{i-1}-l_{i-1}+1)} gi=(ri−li+1)(ri−1−li−1+1)v=li∑ri(j=li−1∑ri−1fi−1,j)+v=li∑rij=li−1∑ri−1∣v−j∣
好鬼冗长的式子
红色部分：
∑ v = l i r i ∑ j = l i − 1 r i − 1 f i − 1 , j = ∑ v = l i r i ( r i − 1 − l i − 1 + 1 ) g i − 1 = ( r i − l i + 1 ) ( r i − 1 − l i − 1 + 1 ) g i − 1 \sum\limits_{v=l_{i}}^{r_{i}}\sum\limits_{j=l_{i-1}}^{r_{i-1}}f_{i-1,j}=\sum\limits_{v=l_{i}}^{r_{i}}(r_{i-1}-l_{i-1}+1)g_{i-1}=(r_{i}-l_{i}+1)(r_{i-1}-l_{i-1}+1)g_{i-1} v=li∑rij=li−1∑ri−1fi−1,j=v=li∑ri(ri−1−li−1+1)gi−1=(ri−li+1)(ri−1−li−1+1)gi−1
这一部分可以 O ( 1 ) O(1) O(1) 求出。
将重心放在求蓝色式子中，这是本题又一大难点。
先考虑固定 v v v，求 ∑ j = l i − 1 r i − 1 ∣ v − j ∣ \sum\limits_{j=l_{i-1}}^{r_{i-1}} | v-j | j=li−1∑ri−1∣v−j∣，设该数为 h ( v ) h(v) h(v)。如果 v ∈ [ l i − 1 , r i − 1 ] v\in [l_{i-1},r_{i-1}] v∈[li−1,ri−1]，那么我们可以以 v v v 为分界点，把所求变成两个等差数列求和（即分成 [ l i − 1 , v ] [l_{i-1},v] [li−1,v] 和 [ v , r i − 1 ] [v,r_{i-1}] [v,ri−1]）。如果 v < l i − 1 v<l_{i-1} v<li−1 或 v > r i − 1 v>r_{i-1} v>ri−1，那么就是一个等差数列求和的问题。
现在考虑 v v v 从 k k k 变成 ( k + 1 ) (k+1) (k+1) 时求和式变化了多少。
- 如果 k < l i − 1 k<l_{i-1} k<li−1，则所有数到 v v v 的距离都减少了 1 1 1，一共减少了 ( r i − 1 − l i − 1 + 1 ) (r_{i-1}-l_{i-1}+1) (ri−1−li−1+1)，即 h ( k + 1 ) − h ( k ) = − ( r i − 1 − l i − 1 + 1 ) h(k+1)-h(k)=-(r_{i-1}-l_{i-1}+1) h(k+1)−h(k)=−(ri−1−li−1+1)。同理可以求 h ( k + 2 ) h(k+2) h(k+2) 等。 h h h 是一个等差数列，求和问题又可以转化为一个等差数列求和。
- 如果 k ≥ r i − 1 k\geq r_{i-1} k≥ri−1，那么所有数到 v v v 的距离都增加了 1 1 1， h ( k + 1 ) − h ( k ) = r i − 1 − l i − 1 + 1 h(k+1)-h(k)=r_{i-1}-l_{i-1}+1 h(k+1)−h(k)=ri−1−li−1+1。因此 h h h 也是一个等差数列。
- 如果 l i − 1 ≤ k < r i − 1 l_{i-1} \leq k < r_{i-1} li−1≤k<ri−1，则 v v v 从 k k k 变为 ( k + 1 ) (k+1) (k+1) 时， [ l i − 1 , k ] [l_{i-1},k] [li−1,k] 中的数到 v v v 的距离都加 1 1 1，而 ( k , r i − 1 ] (k,r_{i-1}] (k,ri−1] 中的数到 k k k 的距离都减 1 1 1，则 h ( k + 1 ) − h ( k ) = ( k − l i − 1 + 1 ) − ( r i − 1 − k ) = 2 k + 1 − ( r i − 1 + l i − 1 ) h(k+1)-h(k)=(k-l_{i-1}+1)-(r_{i-1}-k)=2k+1-(r_{i-1}+l_{i-1}) h(k+1)−h(k)=(k−li−1+1)−(ri−1−k)=2k+1−(ri−1+li−1)。而 h ( k + 2 ) − h ( k + 1 ) = 2 k + 3 − ( r i − 1 + l i − 1 ) h(k+2)-h(k+1)=2k+3-(r_{i-1}+l_{i-1}) h(k+2)−h(k+1)=2k+3−(ri−1+li−1)。即 Δ h ( k ) = h ( k + 1 ) − h ( k ) \Delta h(k)=h(k+1)-h(k) Δh(k)=h(k+1)−h(k) 构成一个公差为 2 2 2 的等差数列。
直接考虑求 ∑ v = l r h ( v ) \sum\limits_{v=l}^{r} h(v) v=l∑rh(v)。
∑ v = l r h ( v ) = ∑ v = l r h ( l ) + ( ∑ j = l v − 1 Δ h ( j ) ) = ( r − l + 1 ) h ( l ) + ∑ v = l r ( ∑ j = l v − 1 Δ h ( l ) + 2 ( j − l ) ) \sum\limits_{v=l}^{r} h(v)=\sum\limits_{v=l}^{r}h(l)+\left ( \sum\limits_{j=l}^{v-1} \Delta h(j) \right )=(r-l+1)h(l)+\sum\limits_{v=l}^{r} \left ( \sum\limits_{j=l}^{v-1} \Delta h(l)+2(j-l) \right ) v=l∑rh(v)=v=l∑rh(l)+(j=l∑v−1Δh(j))=(r−l+1)h(l)+v=l∑r(j=l∑v−1Δh(l)+2(j−l))。
Δ h ( l ) \Delta h(l) Δh(l) 是一个定值，因此 ∑ v = l r ∑ j = l v − 1 Δ h ( l ) \sum\limits_{v=l}^{r} \sum\limits_{j=l}^{v-1} \Delta h(l) v=l∑rj=l∑v−1Δh(l) 又是一个等差数列求和。
而 ∑ v = l r ∑ j = l v − 1 2 ( j − l ) = ∑ v − l r ( v − l ) ( v − l − 1 ) = ∑ i = 1 r − l − 1 i ( i + 1 ) = ∑ i = 1 r − l − 1 i 2 + ∑ i = 1 r − l − 1 i \sum\limits_{v=l}^{r}\sum\limits_{j=l}^{v-1}2(j-l)=\sum\limits_{v-l}^{r}(v-l)(v-l-1)=\sum\limits_{i=1}^{r-l-1}i(i+1)=\sum\limits_{i=1}^{r-l-1}i^{2}+\sum\limits_{i=1}^{r-l-1} i v=l∑rj=l∑v−12(j−l)=v−l∑r(v−l)(v−l−1)=i=1∑r−l−1i(i+1)=i=1∑r−l−1i2+i=1∑r−l−1i。这样就可以转化为直接可以用公式求解的问题。
最后一个问题是 [ l i , r i ] [l_{i},r_{i}] [li,ri] 和 [ l i − 1 , r i − 1 ] [l_{i-1},r_{i-1}] [li−1,ri−1] 的包含关系非常混乱，不止上面讨论的三种。怎么办？
很简单，把 [ l i , r i ] [l_{i},r_{i}] [li,ri] 拆成 [ l i , l i − 1 ) , [ l i − 1 , r i − 1 ) , [ r i − 1 , r i ] [l_{i},l_{i-1}),[l_{i-1},r_{i-1}),[r_{i-1},r_{i}] [li,li−1),[li−1,ri−1),[ri−1,ri] 三段即可，每种都是上面讨论的三种情况中的一种，可以直接求解。单次求解的时间复杂度为 O ( 1 ) O(1) O(1)。
总的时间复杂度为 O ( n ) O(n) O(n)，可以愉快地跑过（前提是代码别写错，这题十分考验码力）。
[Code] \color{blue}{\text{[Code]}} [Code]
int ksm(int a,int b){int ret=1;while (b){if (b&1) ret=1ll*ret*a%mod;a=1ll*a*a%mod;b>>=1;}return ret;
}int f[N],n,l[N],r[N];int calc(int n){if (n<=0) return 0;int a=1ll*n*(n+1)%mod*(2ll*n%mod+1)%mod*ksm(6,mod-2)%mod;int b=1ll*n*(n+1)%mod*ksm(2,mod-2)%mod;return (a+b)%mod;
}int calc(int l,int r,int L,int R){if (l>r) return 0;int ans=0,tmp;if (L<=l&&r<=R){tmp=(1ll*(l-L)*(l-L+1)%mod*ksm(2,mod-2)%mod+1ll*(R-l)*(R-l+1)%mod*ksm(2,mod-2)%mod)%mod;ans=(((1ll*(r-l+1)*tmp%mod+1ll*(r-l)*(r-l+1)%mod*ksm(2,mod-2)%mod*(2*l-R-L+1)%mod)%mod+mod)%mod+calc(r-l-1))%mod;}else if (r<=L){tmp=(1ll*(L-r)*(R-L+1)%mod+1ll*(R-L)*(R-L+1)%mod*ksm(2,mod-2)%mod)%mod;ans=(1ll*tmp*(r-l+1)%mod+1ll*(R-L+1)*(r-l)%mod*(r-l+1)%mod*ksm(2,mod-2)%mod)%mod;}else if (l>=R){tmp=(1ll*(l-R)*(R-L+1)%mod+1ll*(R-L)*(R-L+1)%mod*ksm(2,mod-2)%mod)%mod;ans=(1ll*tmp*(r-l+1)%mod+1ll*(R-L+1)*(r-l)%mod*(r-l+1)%mod*ksm(2,mod-2)%mod)%mod;}//式子特别多特别长，别写错，记得随时取模return ans;
}int main(){int T=read();while (T--){n=read();f[1]=0;for(int i=1,rec;i<=n;i++){l[i]=read();r[i]=read();if (i>=2){if (l[i]>=l[i-1]){if (l[i]>=r[i-1]) rec=calc(l[i],r[i],l[i-1],r[i-1]);else if (r[i]<=r[i-1]) rec=calc(l[i],r[i],l[i-1],r[i-1]);else rec=(calc(l[i],r[i-1]-1,l[i-1],r[i-1])+calc(r[i-1],r[i],l[i-1],r[i-1]))%mod;}else{if (r[i]<=l[i-1]) rec=calc(l[i],r[i],l[i-1],r[i-1]);else if (r[i]<=r[i-1]) rec=(calc(l[i],l[i-1]-1,l[i-1],r[i-1])+calc(l[i-1],r[i],l[i-1],r[i-1]))%mod;else rec=((calc(l[i],l[i-1]-1,l[i-1],r[i-1])+calc(l[i-1],r[i-1],l[i-1],r[i-1]))%mod+calc(r[i-1]+1,r[i],l[i-1],r[i-1]))%mod;}f[i]=(f[i-1]+1ll*rec*ksm(r[i-1]-l[i-1]+1,mod-2)%mod*ksm(r[i]-l[i]+1,mod-2)%mod)%mod;}}printf("%d\n",f[n]);}return 0;
}
