首页 > 其他 > 详细

BZOJ2616PERIODNI

时间:2019-02-20 22:31:54      阅读:215      评论:0      收藏:0      [点我收藏+]

题目描述

给定一个N列的表格,每列的高度各不相同,但底部对齐,然后向表格中填入K个相同的数,填写时要求不能有两个数在同一列,或同一行,下图中b是错误的填写,a是正确的填写,因为两个a虽然在同一行,但它们中间的表格断开。

输出所有填写方案数对1 000 000 007的余数。

输入:?第一行两个整数 N 和 K (1 ≤ N ≤ 500, 1 ≤ K ≤ 500),表示表格的列数和要填写的数的个数。?接下来一行N个数,表示每列的高度。高度不超过 1 000 000.

输出:?一个整数,方案总数对1000 000 007的余数。

题解

这种问题不好在序列上直接处理,考虑每次从当前序列中找出最小的数作为根,递归构造两边的子树。

这样构造出来的数叫笛卡尔树,保证了中序遍历是原序列,整颗树又满足堆的性质。

因为我们需要的树是静态的,所以构建笛卡尔树的复杂度可以降到O(n),具体构建的方法和虚树基本一致,就用栈维护一下当前的右链就可以了。

然后dp就变得十分容易,设dp[i][j]表示i子树内放j个的方案数,注意:我们每往下递归一层,宽度就要减去h[i],这样方便转移。

答案可能来自三部分,左子树、右子树和自己,转移时讨论一下就好了。

代码

#include<iostream>
#include<cstdio>
#define N 502
using namespace std;
const int mod=1e9+7;
typedef long long ll;
const int maxn=1000000;
ll dp[N][N],jie[maxn+2],ni[maxn+2];
int ch[N][2],a[N],n,size[N],k,st[N],top;
inline int rd(){
    int x=0;char c=getchar();bool f=0;
    while(!isdigit(c)){if(c==-)f=1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f?-x:x;
}
inline ll power(ll x,ll y){
    ll ans=1;
    while(y){if(y&1)ans=ans*x%mod;x=x*x%mod;y>>=1;}
    return ans;
}
inline ll C(int n,int m){if(n<m)return 0;return jie[n]*ni[m]%mod*ni[n-m]%mod;}
void dfs(int u,int fa){
    size[u]=1;
    if(ch[u][0])dfs(ch[u][0],u),size[u]+=size[ch[u][0]];if(ch[u][1])dfs(ch[u][1],u),size[u]+=size[ch[u][1]];
    for(int i=0;i<=size[u];++i)
      for(int j=0;j<=i;++j)(dp[u][i]+=dp[ch[u][0]][j]*dp[ch[u][1]][i-j]%mod)%=mod;
    for(int i=size[u];i>=0;--i)
      for(int j=0;j<i;++j)(dp[u][i]+=dp[u][j]*jie[i-j]%mod*C(size[u]-j,i-j)%mod*C(a[u]-a[fa],i-j)%mod)%=mod;
}
int main(){
    n=rd();k=rd();
    dp[0][0]=1;
    for(int i=1;i<=n;++i)a[i]=rd();
    jie[0]=1;
    for(int i=1;i<=maxn;++i)jie[i]=jie[i-1]*i%mod;ni[maxn]=power(jie[maxn],mod-2);
    for(int i=maxn-1;i>=0;--i)ni[i]=ni[i+1]*(i+1)%mod;
    for(int i=1;i<=n;++i){
        while(top&&a[i]<a[st[top]]){
            int x=st[top];top--;
            if(top&&a[i]<a[st[top]])ch[st[top]][1]=x;
            else ch[i][0]=x;
        }
        st[++top]=i;
    }
    while(top>1){ch[st[top-1]][1]=st[top];top--;}
    dfs(st[1],0);
    printf("%lld",dp[st[1]][k]);
    return 0;
    
}

BZOJ2616PERIODNI

原文:https://www.cnblogs.com/ZH-comld/p/10409392.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!