首页 > 代码库 > HDU 5729 Rigid Frameworks（连通性DP）
HDU 5729 Rigid Frameworks（连通性DP）
【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=5729
【题目大意】
给出一个n*m的方格框，可以在单位矩形中添加两种对角线的线，使得其变得稳定，问使得其变成稳定图形的方案数。
【题解】
稳定状态指的是在n*m范围内每行每列都有一个固定的格子，并且联动，计算合法的情况非常的复杂，难以枚举，因此我们可以枚举非法情况，从组合数中减去即可。非法情况即将图形划分为合法部分和非法部分，注意枚举全面。
【代码】
#include <cstdio>using namespace std;#define rep(i,n) for(int i=1;i<=n;i++)const long long mod=1e9+7;long long dp[15][15][105],c[105][105];int n,m;long long pow(long long a,long long b){ long long tmp=1; a%=mod; while(b){ if(b&1)tmp=tmp*a%mod; a=a*a%mod; b>>=1; }return tmp;}int main(){ rep(i,100){ c[i][0]=c[i][i]=1; rep(j,i-1)c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod; }c[0][0]=dp[1][0][0]=dp[0][1][0]=1; rep(i,10)rep(j,10){ if(i==1||j==1){dp[i][j][i+j-1]=1;continue;} rep(k,i*j){ dp[i][j][k]=c[i*j][k]; rep(ii,i)for(int jj=0;jj<=j;jj++){ if(i+j==ii+jj)continue; for(int kk=0;kk<=k;kk++){ long long tmp=c[i-1][ii-1]*c[j][jj]%mod; tmp=tmp*dp[ii][jj][kk]%mod; tmp=tmp*c[(i-ii)*(j-jj)][k-kk]%mod; dp[i][j][k]=(dp[i][j][k]+mod-tmp)%mod; } } } }while(~scanf("%d%d",&n,&m)){ long long ans=0; rep(i,n*m)ans=(ans+pow(2,i)*dp[n][m][i]%mod)%mod; printf("%lld\n",ans); }return 0;}
HDU 5729 Rigid Frameworks（连通性DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。