UOJ #204. 【APIO2016】Boat dp+组合数学

题意

给你n个区间，每个区间可以选的数的范围是[ai,bi]要你求非空上升子序列的个数

n<=500,ai,bi<=10^9

分析

这道题好题啊，但是我好弱啊

先说部份分，对于每个数我们可以拆成两维，(pos,num),然后就可以dp来做，每一次只把pos和num比较小的累计起来，然后简单的二维dp

考虑下正解，肯定是把很多区间给离散化一下，但是这里又害怕取到相同的数，我们可以先把bi+1，然后对于每个区间，就是取 [li,ri) [ l i , r i )

然后现在看怎么dp， f[i][j] f [ i ] [ j ] 表示第i个数必须放，放的高度在j区间里面，枚举上一个放的区间

f[i][j]=∑k=0i(∑p=0jf[k][p])calc(k+1,i,j) f [ i ] [ j ] = ∑ k = 0 i ( ∑ p = 0 j f [ k ] [ p ] ) c a l c ( k + 1 , i , j )

这里的 calc(k+1,i,j) c a l c ( k + 1 , i , j ) 表示 [k+1,i) [ k + 1 , i ) 的数不放，或者范围在第j个区间中，假设 [k+1,i) [ k + 1 , i ) 能放的有 m m 个,当前j这个区间的长度为l

calc(k+1,i,j)=∑i=1m+1(mi−1)(li)calc(k+1,i,j)=∑i=1m+1(mi−1)(li)

这里好像有范德蒙德卷积公式：

calc(k+1,i,j)=(m+lm+1) c a l c ( k + 1 , i , j ) = ( m + l m + 1 )

f[i][j]=∑k=0i(∑p=0jf[k][p])(m+lm+1) f [ i ] [ j ] = ∑ k = 0 i ( ∑ p = 0 j f [ k ] [ p ] ) ( m + l m + 1 )

发现这里括号内可以维护个前缀和，就没了

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = ;
const ll Mod = e9+;
inline ll read()
{
  char ch=getchar(); ll p=; ll f=;
  while(ch<'0' || ch>'9'){if(ch=='-') f=-; ch=getchar();}
  while(ch>='0' && ch<='9'){p=p*10+ch-'0'; ch=getchar();}
  return p*f;
}
ll n,a[N],b[N],h[N],c[N];
ll f[N][N],inv[N];
void upd(ll &x,ll y){x = (x+y) % Mod;}
int main()
{
  n = read();
  inv[] = inv[] = ; for(ll i=;i<=n+;i++) inv[i] = (Mod - Mod / i) * inv[Mod % i] % Mod;
  for(ll i=;i<=n;i++) a[i] = read() , b[i] = read() , b[i] ++ ,  h[i*2-] = a[i],h[i*2] = b[i];
  sort(h+,h+*n+);
  ll len = unique(h+,h+*n+) - (h+);
  for(ll i=;i<=n;i++)
  {
    a[i] = lower_bound(h+,h+len+,a[i]) - h;
    b[i] = lower_bound(h+,h+len+,b[i]) - h - ;
    // printf("%lld %lld\n",a[i],b[i]);
  }

  len --; for(ll i=;i<=len;i++) c[i] = h[i+] - h[i] ;

  for(ll i=;i<=len;i++) f[][i] = ;
  for(ll i=;i<=n;i++)
  {
    for(ll j=a[i];j<=b[i];j++)
    {
      ll m = ; ll sum = c[j];
      for(ll k=i-;k>=;k--)
      {
        upd(f[i][j],f[k][j-] * sum % Mod);
        if(a[k] <= j && j <= b[k])
        {
          m++;
          sum = sum * ((c[j] + m) % Mod) % Mod * inv[m+] % Mod;
        }
      }
    }
    for(ll j=;j<=len;j++) upd(f[i][j] , f[i][j-]);
  }

  ll ans = ;
  for(ll i=;i<=n;i++)
  {
    // printf("%lld\n",f[i][len]);
    upd(ans , f[i][len]);
  }

  return printf("%lld\n",ans),;
}