题目
点这里看题目。
分析
初看似乎只能想到一个暴躁的 DP ：
(f(i,j)) ：前 (i) 个数，最后一个数是 (j) 的序列方案数。
...... 嗯，显然会 TLE 。
不过，由于总共的区间数很少，所以由区间的端点组合的区间会很少。我们可以从这个方向入手压缩状态。
考虑将原先的闭区间 ([l_i,r_i]) 转为开区间 ([l'_i,r'_i)) 。然后将所有的 (l'_i) 和 (r'_i) 拿出来排序并去重，得到了序列 (P) 。并记 (I_j=[P_{j},P_{j+1})) 。我们于是可以考虑重新定义状态：
(f(i,j)) ：前 (i) 个数，最后一个数落在了 (I_j) 中的方案数。
转移时我们可以考虑枚举属于 (I_j) 的数的范围。同一个区间中选取出不增序列的方案数可以隔板法计算，本质上求出 ([l,r)) 中随便选出 (c) 个数组成不增子序列等价于从 ([l,r)) 中随便选出 (c) 个数，也即是 (inom{r-l+c-1}{c}) 。具体写出来就长这个样子：
[f(i,j)=sum_{k=0}^{i-1}[forall k<ple i,I_jsubset [l_p,r_p]]sum_{j<t}f(k,t)inom{|I_j|+i-k}{i-k}
]
最终的答案就是 (sum_{j}f(n,j)) 除以总的序列数。
实际转移的时候，我们可以在发现 ([forall k<ple i,I_{j}subset[l_p,r_p]]= 0) 时直接跳出。后面的 (sum_{j<t} f(k,t)) 可以运用后缀和优化。 (inom{|I_j|+i-k}{i-k}) 需要 (O(n)) 单独计算。
因此转移的时间复杂度是 (O(n^4)) 。
小结：
- 第二维状态表示区间而非某个数，以此压缩了状态，比较有意义。
- 计算确定区间内合法序列个数的转化，比较有意义。
代码
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int mod = 998244353;
const int MAXN = 105;
template<typename _T>
void read( _T &x )
{
x = 0; char s = getchar(); int f = 1;
while( s < '0' || '9' < s ) { f = 1; if( s == '-' ) f = -1; s = getchar(); }
while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ); s = getchar(); }
x *= f;
}
template<typename _T>
void write( _T x )
{
if( x < 0 ) putchar( '-' ), x = -x;
if( 9 < x ) write( x / 10 );
putchar( x % 10 + '0' );
}
template<typename _T>
_T MAX( const _T a, const _T b )
{
return a > b ? a : b;
}
template<typename _T>
_T MIN( const _T a, const _T b )
{
return a < b ? a : b;
}
int f[MAXN][MAXN];
int l[MAXN], r[MAXN], pnt[MAXN << 1];
int lef[MAXN], rig[MAXN];
int N;
int Qkpow( int base, int indx );
int Inv( const int a ) { return Qkpow( a, mod - 2 ); }
int Mul( LL x, int v ) { x *= v; if( x >= mod ) x %= mod; return x; }
int Add( int x, int v ) { return x + v >= mod ? x + v - mod : x + v; }
int Qkpow( int base, int indx )
{
int ret = 1;
while( indx )
{
if( indx & 1 ) ret = Mul( ret, base );
base = Mul( base, base ), indx >>= 1;
}
return ret;
}
int C( const int n, const int m )
{
if( n < m ) return 0; int ret = 1;
for( int i = 1 ; i <= m ; i ++ )
ret = Mul( ret, Mul( n - i + 1, Inv( i ) ) );
return ret;
}
int main()
{
read( N ); int tot = 0;
for( int i = 1 ; i <= N ; i ++ ) read( l[i] ), read( r[i] );
for( int i = 1 ; i <= N ; i ++ ) pnt[++ tot] = l[i], pnt[++ tot] = r[i] + 1;
sort( pnt + 1, pnt + 1 + tot );
tot = unique( pnt + 1, pnt + 1 + tot ) - pnt - 1;
for( int i = 1 ; i <= N ; i ++ )
lef[i] = lower_bound( pnt + 1, pnt + 1 + tot, l[i] ) - pnt,
rig[i] = lower_bound( pnt + 1, pnt + 1 + tot, r[i] + 1 ) - pnt;
int ans = 0, L;
lef[0] = 1, rig[0] = tot + 1;
for( int i = 1 ; i <= tot ; i ++ ) f[0][i] = 1;
for( int i = 1 ; i <= N ; i ++ )
{
for( int j = lef[i] ; j < rig[i] ; j ++ )
{
L = pnt[j + 1] - pnt[j];
for( int k = i ; k ; k -- )
{
if( j < lef[k] || rig[k] <= j ) break;
f[i][j] = Add( f[i][j], Mul( f[k - 1][j + 1], C( i - k + L, i - k + 1 ) ) );
}
}
for( int j = tot - 1 ; j ; j -- )
f[i][j] = Add( f[i][j + 1], f[i][j] );
}
ans = f[N][1];
for( int i = 1 ; i <= N ; i ++ )
ans = Mul( ans, Inv( r[i] - l[i] + 1 ) );
write( ans ), putchar( '
' );
return 0;
}