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),;
}