2018.10.24 bzoj3195: [Jxoi2012]奇怪的道路(状压dp)
2024-10-15 06:48:46
传送门
f[i][j][k]f[i][j][k]f[i][j][k]表示前iii个点连了jjj条边,第i−K+1i-K+1i−K+1~iii个点连边数的奇偶性为kkk时的方案数。
转移规定只能从后向前连边。
然后讨论奇偶性转移就行了。
注意从f[i−1]f[i-1]f[i−1]转移过来的时候不用考虑最前面一位。
然后再用f[i][j]f[i][j]f[i][j]转移f[i][j+1]f[i][j+1]f[i][j+1]就行了。
代码:
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
const int mod=1e9+7;
int n,m,K,f[35][35][(1<<9)+5];
int main(){
n=read(),m=read(),K=read();
int up=1<<(K+1);
f[1][0][0]=1;
for(int i=2;i<=n;++i){
for(int k=0;k<up;++k)if(!(k&1))for(int j=0;j<=m;++j)if(f[i-1][j][k])(f[i][j][k>>1]+=f[i-1][j][k])%=mod;
for(int l=1;l<=K;++l)if(i>l)for(int j=0;j<m;++j)for(int k=0;k<up;++k)
if(f[i][j][k])(f[i][j+1][k^(1<<K)^(1<<(K-l))]+=f[i][j][k])%=mod;
}
cout<<f[n][m][0];
return 0;
}
最新文章
- gulp安装说明
- CSS实现DIV水平自适应居中
- FZU 1686 神龙的难题 (重复覆盖)
- Http协议的常见参数
- Window Ghosting
- 录制简单的自动化测试工具SlikMobile初体验
- Mininet建立topology zoo中的拓扑
- PTPX的average power analysis
- Open vSwitch FAQ (三)
- iOS学习之基础控件
- 今天开始自学Andrew Ng的机器学习,希望可以坚持下来
- PendingIntent Bundle null解决方案
- 完整的RecylerView的使用方法和例子
- [置顶]
 Xamarin android 调用Web Api(ListView使用远程数据)
- Activity简介
- nginx系列12:一致性哈希算法
- gmtdefaults locate
- python opencv3 给图片加中文
- QQ登录整合/oauth2.0认证-04-调整到QQ互联进行QQ登录
- win8 无法显示桌面,运行explorer.exe 提示 0xc0000018 异常 解决办法
热门文章
- Chrome格式化JavaScript代码
- 记录下ABAP开发的一些东西(T-code居多)Updated to markdown
- java中钩子方法的概念
- Linux 任务管理 &;&; 常用指令
- 10.Mysql索引
- find和find_if,value_type
- Andriod ----配置环境变量
- hdu 1255(线段树 扫描线) 覆盖的面积
- 百度云的ubuntu16.04.1部署Apache服务器+Django项目
- yii2.0增删改查