HDU5731 Solid Dominoes Tilings 状压dp+状压容斥
2024-03-27 18:28:05
题意：给定n,m的矩阵，就是求稳定的骨牌完美覆盖,也就是相邻的两行或者两列都至少有一个骨牌
分析：第一步：
如果是单单求骨牌完美覆盖，请先去学基础的插头dp(其实也是基础的状压dp)骨牌覆盖
hihocoder有全套课程：骨牌覆盖（一, 二，三），状态压缩（二）
学好了以后，首先打一个预处理没有限制的表，由于赛后补题，我就没自己打，直接从网上粘的表
我的表来自：http://blog.csdn.net/u012015746/article/details/51971977
第二步：
这就是容斥的过程了，我们可以枚举每种列分割状态，计算出每种列分割状态下行合法的方案数
然后用总数，减去一个列分割数为1的，加上列分割数为2.........这就是容斥的过程了
细节处理：每种列状态下如何求合法的行状态呢，每种状态在用一下递推一下就好了（枚举依据是前j行无行分割，后i-j行有行分割）
其实是枚举的第一个行分割线出现的位置，上面不能有，下面就可以随意了
详情请参考上面的链接
复杂度：O（T*(n^2)*(2^m))，大概是这个复杂度
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL mod = 1e9+;
LL RES[][];
void init();
LL dp[];
LL solve(int n,int m){
int pos[],tot=(<<(m-));
LL ret=;
for(int cur=;cur<tot;++cur){
int cnt=;pos[cnt]=;
for(int i=;i<m-;++i)if(cur&(<<i))pos[++cnt]=i+;
pos[++cnt]=m;
for(int i=cnt;i>;--i)pos[i]-=pos[i-];
for(int i=;i<=n;++i){
for(int j=;j<i;++j){
LL tmp=;
for(int k=;k<=cnt;++k)
tmp=tmp*RES[i-j][pos[k]]%mod;
if(!j)dp[i]=tmp;
else dp[i]=(dp[i]-tmp*dp[j]%mod+mod)%mod;
}
}
if(cnt&)ret=(ret-dp[n]+mod)%mod;
else ret=(ret+dp[n])%mod;
}
return ret;
}
int main(){
init();
int n,m;
while(~scanf("%d%d",&n,&m)){
printf("%I64d\n",solve(n,m));
}
return ;
}
void init()
{
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
RES[][] = ;
}
最新文章
- 背水一战 Windows 10 (19) - 绑定: TemplateBinding 绑定, 与 RelativeSource 绑定, 与 StaticResource 绑定
- Swift 必备开发库10个
- UI2_IOS坐标系
- 【ActiveX】实现安全接口
- keil c51 本變數型態(Variable Type)
- IIS发布网站后局域网其他用户不能访问问题（转）
- OBIEE 缓存机制
- Android.mk简单分析
- JS画几何图形之三【正弦曲线】
- 《android开发艺术探索》读书笔记（十四）--JNI和NDK编程
- MySQL的sum()函数
- 【转】RTP学习笔记
- mybatis源码-Mapper解析之SQL 语句节点解析（一条语句对应一个MappedStatement)
- 如何用MTR诊断网络问题
- Java CompletableFuture：allOf等待所有异步线程任务结束
- Python基础（2）——列表、字典、数据运算
- 电脑cpu100%的原因
- tensorflow 单机多GPU mnist实例
- 从理论到实践，全方位认识DNS
- python 序列化 pickle shelve json configparser