[APIO2016]划艇-程序员宅基地

[APIO2016]划艇 

总共只有2*n段。分段进行DP

简单的方法是：

外层枚举段数j，f[i]表示，当前枚举到j的时候，以(i,j)结尾（必须选择(i,j)）的方案数，枚举一个f(p,1~j-1)进行转移

连续一段j区间，有包括i一共有m个可以选择的学校，那么这里贡献的方案数就是：∑(1<=i<=m)C(len,i)*C(m-1,i)=C(l+m-1,m)等式考虑用网格图走来证明

C可以预处理

#include<bits/stdc++.h>
#define reg register int
#define il inline
#define fi first
#define se second
#define mk(a,b) make_pair(a,b)
#define numb (ch^'0')
using namespace std;
typedef long long ll;
template<class T>il void rd(T &x){
    char ch;x=0;bool fl=false;
    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
    for(x=numb;isdigit(ch=getchar());x=x*10+numb);
    (fl==true)&&(x=-x);
}
template<class T>il void output(T x){
    if(x/10)output(x/10);putchar(x%10+'0');}
template<class T>il void ot(T x){
    if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}
template<class T>il void prt(T a[],int st,int nd){
    for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}

namespace Miracle{
const int N=1003;
const int mod=1e9+7;
int n;
int lo[N],hi[N],c[2*N],cnt;
int C[N];
int ad(int x,int y){
    return x+y>=mod?x+y-mod:x+y;
}
int mul(int x,int y){
    return (ll)x*y%mod;
}
int g[N];
int inv[N];
int main(){
    rd(n);
    inv[1]=1;
    for(reg i=2;i<=n;++i){
        inv[i]=mul(mod-mod/i,inv[mod%i]);
    }
    for(reg i=1;i<=n;++i){
        rd(lo[i]);rd(hi[i]);
        c[++cnt]=lo[i];c[++cnt]=hi[i]+1;
    }
    sort(c+1,c+cnt+1);
    cnt=unique(c+1,c+cnt+1)-c-1;
    for(reg i=1;i<=n;++i){
        lo[i]=lower_bound(c+1,c+cnt+1,lo[i])-c;
        hi[i]=lower_bound(c+1,c+cnt+1,hi[i]+1)-c;
    }
    g[0]=1;C[0]=1;
    // cout<<" cnt "<<cnt<<endl;
    // prt(lo,1,n);
    // prt(hi,1,n);
    for(reg j=1;j<cnt;++j){
        int len=c[j+1]-c[j];
        // cout<<" len "<<len<<" in "<<j<<endl;
        C[0]=len;
        for(reg i=1;i<=n;++i) C[i]=mul(C[i-1],mul(len+i,inv[i+1]));
        // cout<<" C ";prt(C,0,n);
        for(reg i=n;i>=1;--i){
            if(lo[i]<=j&&j<hi[i]){
                int f=0,m=0;
                for(reg p=i-1;p>=0;--p){
                    f=ad(f,mul(C[m],g[p]));
                    if(lo[p]<=j&&j<hi[p]) ++m;
                }
                g[i]=ad(g[i],f);
                // cout<<" con "<<i<<" "<<f<<endl;
            }
        }
        // cout<<"gg "<<endl;
        // prt(g,1,n);
    }
    int ans=0;
    for(reg i=1;i<=n;++i) ans=ad(ans,g[i]);
    ot(ans);return 0;
}

}
signed main(){
    Miracle::main();
    return 0;
}

/*
   Author: *Miracle*
*/