BZOJ2616: SPOJ PERIODNI

BZOJ2616: SPOJ PERIODNI

https://lydsy.com/JudgeOnline/problem.php?id=2616

分析:

• 好题，以最小值为根建出笛卡尔树，转化成矩形问题，那么两棵子树之间就不会产生相互攻击的情况。
• 这是一个比较经典的模型，笛卡尔树上每一个点维护一个矩形，上边界为权值，下边界为父亲的权值，左右边界为控制子树范围。
• 那么就可以\(DP\)了，设\(f[i][j]\)表示\(i\)子树中选了\(j\)个点，先转移出两棵子树中选了若干个点的方案数，剩下的在矩形中任选，方案是组合数乘排列数，这个式子也比较好理解。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;
#define N 550
#define M 1000050
#define mod 1000000007
typedef long long ll;
int n,K,a[N],S[N],tp,ls[N],rs[N],siz[N];ll fac[M],inv[M],f[N][N],tmp[N];
ll qp(ll x,ll y) {ll re=1;for(;y;y>>=1,x=x*x%mod) if(y&1) re=re*x%mod; return re;}
ll C(int x,int y) {return x<y?0:fac[x]*inv[y]%mod*inv[x-y]%mod;}
void dfs(int p,int dep) {
    if(!p) return ;
    dfs(ls[p],a[p]); dfs(rs[p],a[p]);
    int h=a[p]-dep,i,j;
    siz[p]=siz[ls[p]]+siz[rs[p]]+1;
    for(i=0;i<=siz[p];i++) tmp[i]=0;
    for(i=0;i<=siz[ls[p]];i++) for(j=0;j<=siz[rs[p]];j++) {
        tmp[i+j]=(tmp[i+j]+f[ls[p]][i]*f[rs[p]][j])%mod;
    }
    for(i=0;i<=siz[p];i++) {
        for(j=0;j<=i;j++) {
            f[p][i]=(f[p][i]+tmp[i-j]*fac[j]%mod*C(h,j)%mod*C(siz[p]-(i-j),j))%mod;
        }
    }
}
int main() {
    int i;
    for(fac[0]=i=1;i<M;i++) fac[i]=fac[i-1]*i%mod;
    inv[M-1]=qp(fac[M-1],mod-2);
    for(i=M-2;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
    scanf("%d%d",&n,&K);
    for(i=1;i<=n;i++) {
        scanf("%d",&a[i]);
        while(tp&&a[i]<=a[S[tp]]) {
            if(tp==1||a[i]>a[S[tp-1]]) {
                ls[i]=S[tp]; tp--; break;
            }
            rs[S[tp-1]]=S[tp]; tp--;
        }
        S[++tp]=i;
    }
    while(tp>1) rs[S[tp-1]]=S[tp],tp--;
    int rt=S[1];
    f[0][0]=1;
    dfs(rt,0);
    printf("%lld\n",(f[rt][K]+mod)%mod);
}

BZOJ2616: SPOJ PERIODNI

原文：https://www.cnblogs.com/suika/p/10264140.html