首页 > 代码库 > BZOJ2616 : SPOJ PERIODNI
BZOJ2616 : SPOJ PERIODNI
长为$A$,宽为$B$的矩阵放$K$个车的方案数$=C(A,K)\times C(B,K)\times K!$。
建立笛卡尔树,那么左右儿子独立,设$f[i][j]$表示$i$子树内放$j$个车的方案数。
合并左右儿子之后,枚举在底部矩形放几个车进行转移即可。
时间复杂度$O(n^3)$。
#include<cstdio>const int N=505,M=1000005,P=1000000007;int n,m,i,a[N],mx,fac[M],inv[M],g[N],f[N][N];inline int cal(int a,int b,int k){ if(a<k||b<k)return 0; return 1LL*fac[a]*inv[a-k]%P*inv[k]%P*fac[b]%P*inv[b-k]%P;}int dp(int l,int r,int h){ if(l>r)return 0; int i,j,x=l; for(i=l;i<=r;i++)if(a[i]<a[x])x=i; int u=dp(l,x-1,a[x]),v=dp(x+1,r,a[x]); for(i=0;i<=r-l;i++)g[i]=0; for(i=0;i<=x-l;i++)if(f[u][i])for(j=0;j<=r-x;j++)g[i+j]=(1LL*f[u][i]*f[v][j]+g[i+j])%P; for(i=0;i<=r-l+1;i++)for(f[x][i]=j=0;j<=r-l&&j<=i;j++)f[x][i]=(1LL*g[j]*cal(r-l+1-j,a[x]-h,i-j)+f[x][i])%P; return x;}int main(){ scanf("%d%d",&n,&m); for(mx=n,i=1;i<=n;i++)scanf("%d",&a[i]),mx=a[i]>mx?a[i]:mx; for(fac[0]=i=1;i<=mx;i++)fac[i]=1LL*fac[i-1]*i%P; for(inv[0]=inv[1]=1,i=2;i<=mx;i++)inv[i]=1LL*P/i*(P-inv[P%i])%P; for(i=2;i<=mx;i++)inv[i]=1LL*inv[i-1]*inv[i]%P; return printf("%d",f[dp(f[0][0]=1,n,0)][m]),0;}
BZOJ2616 : SPOJ PERIODNI
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。