注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ3902/3347]三向投影  

2015-06-02 21:10:09|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3902: 三向投影

Time Limit: 20 Sec  Memory Limit: 512 MB
Submit: 43  Solved: 19
[Submit][Status][Discuss]

Description

考虑一个由单位立方体构成的立体图形。这个立体图形的底是一个 n 行 m 列的单位平方网
格。每一个单位平方格竖直向上都直立着一些单位立方体(有可能为空)。这个立体图形中每个
单位立方体都属于其竖直向下投影到的单位平方格。每个单位立方体不能架空(即要么底部和另
一个单位立方体接触,要么与底接触)。
你将得到这个立体图形的左视图 (Left View) 和主视图 (Front View),求可能的立体图形数。
下图对应了 n =4;m =5 的一个合法立体图形。

Input

第一行为 n,m。
第二行为 n 个整数,对应左视图,即每一行的最大高度。
第三行为 m 个整数,对应主视图,即每一列的最大高度。

Output

一个数,为可能的立体图形数的个数模 10^9 +9。

Sample Input

4 5 5 2 4 1 5 2 4 0 1

Sample Output

429287

HINT

对于 100% 的数据,1 <= n;m <= 50; 每行每列最大高度不超过 10000。

Solution

易得本题中左视图和正视图中数字的顺序是独立的,故可将两行数字排序后处理。
左/正视图中的第i个数字h限制了俯视图中第i行/列的所有格子不超过高度h,且至少有一格高度为h。
第i行第j列的数字的最大值为d[i][j] = min(左视图第i个数字, 正视图第j个数字),即数字范围是[0, d[i][j]]。若将两行数字从小到大排序后,d[i][j]相同的数字会形成一个个L型。易于发现,d[i][j]不同的格子之间是互不影响的。
现在问题简化为求每个L型的填放方案数,设数字的取值范围为[0, h]。“每行/列至少有一个高度为h的格子”的反面是“每行/每列所有格子高度<h”,后者显然比前者好统计(即数字范围为[0,h-1],方案数=h^格子数)。
故采用容斥法求解,先无视每行每列至少有一高度为h的格子这一限制条件,求出一个总方案数,再减去非法的方案数。求解非法的方案数时,枚举共有i行j列不满足条件(使用组合数学求得非法行列的取法总数),则其余行列满足条件。注意其余行列同样构成一个L型,故转化为了子问题,使用动态规划解决。
可以用Mobius反演来省掉一个n

Code

/**************************************************************
    Problem: 3902
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:996 ms
    Memory:944 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
typedef long long ll;
int n,m,i,j,x,a[10010],b[10010];
ll c[60][60],f[60][60],p=1000000009,ans=1;
ll power(ll t,int k){
    ll f=1;
    for(;k;k>>=1,t=t*t%p)if(k&1)f=f*t%p;
    return f;
}
ll dfs(int n,int m,int a,int b,int h){
    if(f[a][b]!=-1)return f[a][b];
    ll tmp=power(h+1,n*m-(n-a)*(m-b));
    for(int i=0;i<=a;i++)
    for(int j=0;j<=b;j++)if(i||j)
    tmp=(tmp-c[a][i]*c[b][j]%p*power(h,n*m-(n-i)*(m-j))%p*dfs(n-i,m-j,a-i,b-j,h)%p+p)%p;
    return f[a][b]=tmp;
}
int main(){
    scanf("%d%d",&n,&m);
    for(;n--;scanf("%d",&x),a[x]++);
    for(;m--;scanf("%d",&x),b[x]++);
    for(c[0][0]=1,i=1;i<=50;i++)
    for(c[i][0]=1,j=1;j<=i;j++)c[i][j]=(c[i-1][j]+c[i-1][j-1])%p;
    for(n=m=0,i=10000;i;i--)
    if(a[i]||b[i]){
        if(n+=a[i],m+=b[i],!n||!m)return puts("0"),0;
        memset(f,-1,sizeof(f));f[0][0]=1;
        ans=ans*dfs(n,m,a[i],b[i],i)%p;
    }
    printf("%lld\n",ans);
}
/**************************************************************
    Problem: 3902
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:4 ms
    Memory:944 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
typedef long long ll;
int n,m,i,j,x,a[10010],b[10010];
ll c[60][60],f[60][60],p=1000000009,ans=1;
ll power(ll t,int k){
    ll f=1;
    for(;k;k>>=1,t=t*t%p)if(k&1)f=f*t%p;
    return f;
}
ll calc(int n,int m,int a,int b,int h){
    ll ans=0,tmp;
    for(int i=0;i<=a;i++)
    for(int j=0;j<=b;j++){
        tmp=power(h,n*m-(n-i)*(m-j))*power(h+1,(n-i)*(m-j)-(n-a)*(m-b))%p*c[a][i]%p*c[b][j]%p;
        if((i+j)&1)ans=(ans-tmp+p)%p;
        else ans=(ans+tmp)%p;
    }
    return ans;
}
int main(){
    for(scanf("%d%d",&n,&m);n--;scanf("%d",&x),a[x]++);
    for(;m--;scanf("%d",&x),b[x]++);
    for(c[0][0]=1,i=1;i<=50;i++)
    for(c[i][0]=1,j=1;j<=i;j++)c[i][j]=(c[i-1][j]+c[i-1][j-1])%p;
    for(n=m=0,i=10000;i;i--)
    if(a[i]||b[i]){
        if(n+=a[i],m+=b[i],!n||!m)return puts("0"),0;
        memset(f,-1,sizeof(f));f[0][0]=1;
        ans=ans*calc(n,m,a[i],b[i],i)%p;
    }
    printf("%lld\n",ans);
}
  评论这张
 
阅读(203)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018