P13580 [CCPC 2024 重庆站] Median Replacement

本题目来自仓库 https://github.com/Disposrestfully/CCPC-CQ-2024/tree/main

给定一个长为 $n$ 的整数序列 $a_1,a_2,\dots,a_n$，你需要对 $a$ 进行若干次如下操作，使得 $a$ 中所有数均相等： - 选择一段长为**大于 $1$ 的奇数**的区间 $a_l,a_{l+1},\ldots,a_r$，并将此区间内的**所有数**均替换为它们的中位数。 设最终 $a_1=a_2=\ldots=a_n=x$，我们定义序列 $a$ 的值为 $x$ 的最大值。 请你求出所有满足 $\forall\ 1\le i\le n$，$l_i\le a_i\le r_i$ 的整数序列 $a$ 的值之和。 由于答案可能很大，请对 $10^9+7$ 取模。

第一行一个整数 $T$，表示测试数据组数。 对于每组测试数据： - 第一行一个整数 $n$。 - 第二行 $n$ 个整数 $l_1,l_2,\ldots,l_n$。 - 第三行 $n$ 个整数 $r_1,r_2,\ldots,r_n$。 保证$1\le T\le 10$，$3\le n\le 150$，$1\le l_i\le r_i\le 10^9$。

对于每组测试数据，输出一行一个整数表示答案对 $10^9+7$ 取模的结果。

对于第一组测试数据，$a$ 只能为 $[1,1,1]$，值为 $1$，故答案为 $1$。 对于第二组测试数据，$a$ 可以为 $[1,1,1],[1,1,2],[1,2,1],[1,2,2]$，值分别为 $1,1,1,2$，故答案为 $5$。