[Jxoi2012]奇怪的道路 BZOJ3195 状压DP
2024-10-15 02:02:58
分析:
k很小,可以状压。
f[S][i]表示状态S表示在i之前k+1个中点的边数奇偶情况
之后转移的时候,S的最后一位不能为1
附上代码:
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <iostream>
using namespace std;
#define N 35
#define mod 1000000007
#define M 1<<9
int f[N][N][M][10],num,n,m,k;
int main()
{
scanf("%d%d%d",&n,&m,&k);
f[1][0][0][0]=1;
for(int i=1;i<n;i++)
{
for(int j=0;j<=m;j++)
{
for(int S=0;S<1<<(k+1);S++)
{
for(int l=0;l<k;l++)
{
if(!f[i][j][S][l])continue;
f[i][j][S][l+1]=(f[i][j][S][l+1]+f[i][j][S][l])%mod;
if(j<m&&i-k+1+l>=1)
{
(f[i][j+1][S^(1<<k)^(1<<l)][l]+=f[i][j][S][l])%=mod;
}
if(!(S&1))
{
(f[i+1][j][S>>1][0]+=f[i][j][S][k])%=mod;
}
}
}
}
}
printf("%d\n",f[n][m][0][0]);
return 0;
}
最新文章
- 安装SQL Developer,连接Oracle 12c,创建新用户
- layoutSubviews
- C# 去掉List重复元素的方法
- leetcode 102. Binary Tree Level Order Traversal
- 重温WCF之数单向通讯、双向通讯、回调操作(五)
- openfire配置MSSQL说明(数据库设置)
- 夺命雷公狗-----React---10--组建嵌套进行数据遍历
- PHP中使用的变量
- 关于static/const的作用
- linux mysql添加用户
- HBase HFile
- 9.如何解决出现AXIOS的Request header field Content-Type is not allowed by Access-Control-Allow-Headers in preflight response.
- mybatis 使用resultMap实现表间关联
- you&#39;ve successfully authenticated, but Gitee.com does not provide she access.
- BZOJ3196二逼平衡树——线段树套平衡树(treap)
- 【BZOJ3813】【清华集训2014】奇数国 线段树 数学
- JAVA发送http get/post请求,调用http接口、方法
- js动画最佳实现——requestAnimationFrame
- Python基础之模块以及5大模块的使用
- Android-Binder原理浅析
热门文章
- AJAX 简单归纳 -- 前端知识
- Hystrix 框架
- AngularJS图片上传功能实践
- Python&#160;基于python实现ADSL宽带帐号,密码的获取及宽带拨号
- java持有对象【2】ArrayList容器续解
- Vue入门系列(三)之Vue列表渲染及条件渲染实战
- android 解决连接电视机顶盒失败的方法
- python基础一数据类型之字符串
- python 之@staticmethod和@classmethod
- Windows Server 2012无法安装 .NET3.5-安装角色或功能失败,找不到源文件