挺有意思一道题。
直接暴力肯定不行，考虑把区间离散化了，拆成若干左闭右开区间，\(f_{i, j}\) 表示 \(i\) 在第 \(j\) 个区间里，转移考虑枚举上一个不和 \(i\) 在同个区间的数 \(k\)， 则 \([k + 1, i]\) 在一个区间里，相当于把 \(i - k\) 分配成 \(len_j\) 组，每组可以为空，方案数为 \(\dbinom{len_j + i - k - 1}{i - k}\)，前缀和优化一下就是 \(\mathcal{O}(n^3)\) 的了。
然后再看其双倍经验 [APIO2016] 划艇。
这里可以不选但是要求严格单增，相当于 \(000000123\dots len\) 里面选 \(cnt\) 个数，其中 \(0\) 有 \(cnt\) 个，则答案也是 \(\dbinom{len_j + cnt - 1}{cnt}\)，非常奇妙！
给一下后者代码：
点击查看代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
// typedef __int128 i128;
typedef pair<int, int> pii;
const int N = 5e2 + 10, mod = 1e9 + 7;
template<typename T>
void dbg(const T &t) { cout << t << endl; }
template<typename Type, typename... Types>
void dbg(const Type& arg, const Types&... args) {cout << arg << ' ';dbg(args...);
}
namespace Loop1st {
int n, tot;
ll l[N], r[N], c[N << 1], f[N], g[N], fac[N];
ll qpow(ll a, ll b) {ll res = 1;for (; b; b >>= 1, a = a * a % mod) if (b & 1) res = res * a % mod;return res;
}
void main() {cin >> n;fac[0] = 1;for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod;for (int i = 1; i <= n; i++) {cin >> l[i] >> r[i]; r[i]++;c[++tot] = l[i]; c[++tot] = r[i];}sort(c + 1, c + tot + 1); tot = unique(c + 1, c + tot + 1) - c - 1;for (int i = 1; i <= n; i++) {l[i] = lower_bound(c + 1, c + tot + 1, l[i]) - c;r[i] = lower_bound(c + 1, c + tot + 1, r[i]) - c;}f[0] = 1;for (int i = 1; i < tot; i++) {ll len = c[i + 1] - c[i];g[0] = 1;for (int j = 1; j <= n; j++) g[j] = g[j - 1] * (len + j - 1) % mod * qpow(j, mod - 2) % mod;for (int j = n; j; j--) if (l[j] <= i && i < r[j]) {for (int k = j - 1, cnt = 1; ~k; k--) {f[j] = (f[j] + f[k] * g[cnt] % mod) % mod;if (l[k] <= i && i < r[k]) cnt++; // [k + 1, i] 在这个区间里}}}ll ans = 0;for (int i = 1; i <= n; i++) ans = (ans + f[i]) % mod;cout << ans << '\n';
}}
int main() {// freopen("data.in", "r", stdin);// freopen("data.out", "w", stdout);ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int T = 1;// cin >> T;while (T--) Loop1st::main();return 0;
}