NOI2019 机器人
考虑最右的最大值，显然其将序列分成两端，所以可以区间 dp，设 (f_{l,r,k}) 表示区间 ([l,r])，最大值为 (k) 的方案数，显然有转移 (f_{l,r,k}=sum_{mid,k'le k,j<k} f_{l,mid-1,k'} imes f_{mid+1,r,j})，对于每个区间合法的选择最大值的位置只有偏中间的 (4) 个，所以这一部分复杂度为 (mathcal O(n^2W))
然后会发现有效的区间不多，将 dp 换成记搜就可以过这档部分分了，据说有效区间只有 (2000) 个左右。
接下来考虑类似于划艇的做法，将权值区间进行分段（将每个区间视为一个左闭右开的区间 ([l,r))），容易发现至多有 (2n) 个段。
容易发现对于相同的段，显然有转移是相同的，同时考虑 (f_{i,i,kin [l,r)}) 时的取值，显然都是 (1)
每次转移等价于统计一个前缀和并乘起来，考虑将转移按照段落进行划分，对于跨段的转移，对于同段内的每个元素 (i') 其均相同，将之视为常数，那么对于 (i') 产生影响的仅有同段的 (j) 满足 (j<i')，此时转移则等价于在区间内记录前缀，然后再做点值乘法，注意到在 (l=r) 时这是一个常数函数，而转移本质上在做前缀和并进行点值乘法，换而言之本质上这是多项式卷积，次数会增高，简单归纳会发现对于区间 ([l,r])，考虑段 ([L,R]) 时答案是一个关于 (k) 的 (r-l) 次多项式（请注意跨区间必然是常数项，所以会是一个固定的多项式）。
于是转移只需要取 (n) 个点值并相应乘起来，暴力做的话复杂度非常的 (mathcal O(2000 imes n^2))，听说跑不满，我就试着写一发算了。
然后如果直接维护点值，然后暴力插值，可以跑 ( m 95pts)，但是这样每个区间 ([l,r]) 必须要维护 (n) 个点值，我大概要跑 5s，不知道有没有老哥可以通过卡常卡过去。
然而由于题目的性质，大区间的出现次数非常的少，大部分区间都是小区间，所以我们需要去利用每个区间 ([l,r]) 是一个次数不超过 (r-l) 次多项式的这个性质。
考虑直接去维护这个多项式，对于每个区间维护一个多项式 (A_{l,r}(x))，那么转移本质上在进行多项式卷积，计算答案只需要对多项式进行离散积分然后就可以计算答案了。
通过普通幂维护非常的麻烦，所以可以通过下降幂去维护这个多项式，下降幂的离散积分是非常优美的：(int x^{underline{n}}=frac{x^{underline{n+1}}}{n+1})，转移仍然是暴力卷积，复杂度是玄学。
然后转移的时候只需要做下降幂多项式乘法即可，方法很简单，通过乘以 (e^{x}) 暴力转 EGF 点值，在乘以 (e^{-x}) 还原即可。
事实上没有必要卷积，下降幂转点值与系数都是非常方便的，复杂度是 (mathcal O(ncdot sum | m len|^2))
(Code:)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define re register
#define pb push_back
#define int long long
int gi() {
char cc = getchar() ; int cn = 0, flus = 1 ;
while( cc < '0' || cc > '9' ) { if( cc == '-' ) flus = - flus ; cc = getchar() ; }
while( cc >= '0' && cc <= '9' ) cn = cn * 10 + cc - '0', cc = getchar() ;
return cn * flus ;
}
const int N = 300 + 5 ;
const int V = 1500 + 5 ;
const int P = 1e9 + 7 ;
int n, D, dx, top, m, fac[V], inv[V], finv[V], A[N], B[N], K[V], st[V], vis[N][N] ;
int cnt, op, Dp[2205][V], Id[N][N] ;
long long ffS, iv[V] ;
struct node {
int x, y ;
} qwq[V] ;
vector<int> dp[2005] ;
int abc( int x ) {
return ( x > 0 ) ? x : -x ;
}
void inc( int &x, int y ) {
( ( x += y ) >= P ) && ( x -= P ) ;
}
int fpow( int x, int k ) {
int ans = 1, base = x ;
while(k) {
if( k & 1 ) ans = 1ll * ans * base % P ;
base = 1ll * base * base % P, k >>= 1 ;
} return ans ;
}
int Lag( int u, int x, int tp ) {
int fp = 1, ans = 0 ;
for( re int i = 0; i < tp; ++ i ) {
ans = ( ans + 1ll * fp * dp[u][i] % P ) % P,
fp = 1ll * fp * ( x - i ) % P ;
} return ans ;
}
int ffp[V], Ex[V] ;
inline void dft( int u ) {
int l = dp[u].size(), le = l + 6 ;
for( re int i = 0; i < l + le; ++ i )
for( re int j = 0; j <= i && j < l; ++ j ) {
Ex[i] += dp[u][j] * inv[i - j] % P ;
}
dp[u].resize(l + l + 5) ;
for( re int i = 0; i < dp[u].size(); ++ i ) dp[u][i] = Ex[i] % P * fac[i] % P ;
for( re int i = 0; i < l + le; ++ i ) Ex[i] = 0 ;
}
inline void idft( int u ) {
int l = dp[u].size() ;
for( re int i = 0; i < l; ++ i ) dp[u][i] = dp[u][i] * inv[i] % P ;
for( re int i = 0; i < l; ++ i )
for( re int j = 0; j <= i; ++ j )
inc( Ex[i], dp[u][j] * finv[i - j] % P ) ;
for( re int i = 0; i < l; ++ i ) dp[u][i] = Ex[i] ;
for( re int i = 0; i < l; ++ i ) Ex[i] = 0 ;
}
void dfs( int l, int r, int L, int R ) {
if( l > r || vis[l][r] == op ) return ;
int ft = R - L + 1 ;
vis[l][r] = op ; int u = Id[l][r] ;
int lx = max( l, ( r + l - 2 ) / 2 ), rx = min( r, ( r + l + 2 ) / 2 ) ;
dp[u].clear() ;
if( l == r ) {
dp[u].pb(Dp[u][op - 1]) ; int ff = 0 ;
if( A[l] <= L && R <= B[l] ) dp[u].pb(1), ++ ff ;
Dp[u][op] = Lag(u, ft, ff + 1 ), dft(u) ;
dp[u].resize(2 * (r - l) + 4) ;
return ;
}
dp[u].resize(r - l + 3) ;
for( re int i = lx; i <= rx; ++ i ) {
int ll = i - l, rr = r - i ;
if( abc(rr - ll) > 2 ) continue ;
dfs( l, i - 1, L, R ), dfs( i + 1, r, L, R ) ;
if( A[i] > L || B[i] < R ) continue ;
if( i == l )
for( re int j = 1; j <= r - l + 2; ++ j )
inc( dp[u][j], dp[Id[i + 1][r]][j - 1] ) ;
else if( i == r )
for( re int j = 1; j <= r - l + 2; ++ j )
inc( dp[u][j], dp[Id[l][i - 1]][j] ) ;
else
for( re int j = 1; j <= r - l + 2; ++ j )
inc( dp[u][j], 1ll * dp[Id[l][i - 1]][j] * dp[Id[i + 1][r]][j - 1] % P ) ;
}
for( re int i = 1; i <= r - l + 2; ++ i ) inc( dp[u][i], dp[u][i - 1] ) ;
for( re int i = 0; i <= r - l + 2; ++ i ) inc( dp[u][i], Dp[u][op - 1] ) ;
dp[u].resize(r - l + 2), idft(u) ;
Dp[u][op] = Lag(u, ft, r - l + 2), dft(u) ;
dp[u].resize(min( n + 2, 2 * (r - l) + 4)) ;
}
void Dfs( int l, int r ) {
if( l > r || Id[l][r] ) return ;
Id[l][r] = ++ cnt ; if( l == r ) return ;
int lx = max( l, ( r + l - 2 ) / 2 ), rx = min( r, ( r + l + 2 ) / 2 ) ;
for( re int i = lx; i <= rx; ++ i ) {
int ll = i - l, rr = r - i ;
if( abc(rr - ll) > 2 ) continue ;
Dfs( l, i - 1 ) ; Dfs( i + 1, r ) ;
}
}
signed main()
{
n = gi(), D = n + 50 ; fac[0] = inv[0] = iv[0] = 1 ;
rep( i, 1, n ) A[i] = gi(), B[i] = gi(), K[++ top] = A[i], K[++ top] = B[i] + 1 ;
rep( i, 1, D ) fac[i] = 1ll * fac[i - 1] * i % P, inv[i] = fpow( fac[i], P - 2 ) ;
rep( i, 1, D ) iv[i] = fpow( i, P - 2 ) ;
rep( i, 0, D ) finv[i] = (i & 1) ? P - inv[i] : inv[i] ;
sort( K + 1, K + top + 1 ) ;
m = top, top = 0 ;
rep( i, 1, m ) if( K[i] != K[i - 1] ) st[++ top] = K[i] ;
Dfs( 1, n ) ;
for( re int i = 2; i <= top; ++ i )
op = i, dx = min( D, st[i] - st[i - 1] ), dfs( 1, n, st[i - 1], st[i] - 1 ) ;
printf("%lld
", Dp[Id[1][n]][op] % P ) ;
return 0 ;
}