#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<cmath>
#include<cassert>
#include<cstring>
#include<iomanip>
using namespace std;
#ifdef _WIN32
#define i64 __int64
#define out64 "%I64d\n"
#define in64 "%I64d"
#else
#define i64 long long
#define out64 "%lld\n"
#define in64 "%lld"
#endif
#define FOR(i,a,b) for( int i = (a) ; i <= (b) ; i ++)
#define FF(i,a) for( int i = 0 ; i < (a) ; i ++)
#define FFD(i,a) for( int i = (a)-1 ; i >= 0 ; i --)
#define S64(a) scanf(in64,&a)
#define SS(a) scanf("%d",&a)
#define LL(a) ((a)<<1)
#define RR(a) (((a)<<1)+1)
#define SZ(a) ((int)a.size())
#define PP(n,m,a) puts("---");FF(i,n){FF(j,m)cout << a[i][j] << ' ';puts("");}
#define pb push_back
#define CL(Q) while(!Q.empty())Q.pop()
#define MM(name,what) memset(name,what,sizeof(name))
#define read freopen("in.txt","r",stdin)
#define write freopen("out.txt","w",stdout)
const int inf = 0x3f3f3f3f;
const i64 inf64 = 0x3f3f3f3f3f3f3f3fLL;
const double oo = 10e9;
const double eps = 10e-10;
const double pi = acos(-1.0);
const int maxn = 9;
const int maxc = 12;
i64 dp[maxc][1<<maxn];
int n,m;
int seed;
void dfs(int k,int x,int now,int to,bool up,bool down)
{
if(x==m+1)
{
if(!up && !down )
{
dp[k+1][to] += dp[k][now^seed];
}
return ;
}
if(!up && !down)
{
dfs(k,x+1,now<<1,to<<1,false,false);
dfs(k,x+1,now<<1|1,to<<1|1,false,false);
dfs(k,x+1,now<<1|1,to<<1|1,true,false);
dfs(k,x+1,now<<1|1,to<<1|1,false,true);
dfs(k,x+1,now<<1|1,to<<1,true,true);
dfs(k,x+1,now<<1,to<<1|1,true,true);
// dfs(k,x+1,now<<1|1,to<<1,true,false);
dfs(k,x+1,now<<1,to<<1|1,false,true);
// dfs(k,x+1,now<<1|1,to<<1|1,true,true);
}
else if(up && !down)
{
dfs(k,x+1,now<<1|1,to<<1,false,false);
dfs(k,x+1,now<<1|1,to<<1|1,true,true);
dfs(k,x+1,now<<1|1,to<<1|1,false,true);
}
else if(!up && down)
{
dfs(k,x+1,now<<1,to<<1|1,false,false);
// dfs(k,x+1,now<<1|1,to<<1|1,true,false);
dfs(k,x+1,now<<1|1,to<<1|1,true,true);
}
else if(up && down)
{
dfs(k,x+1,now<<1|1,to<<1|1,false,false);
}
return ;
}
i64 start()
{
MM(dp,0);
dp[0][(1<<m)-1]=1;
seed = (1<<m)-1;
FF(i,n)
{
dfs(i,1,0,0,0,0);
}
return dp[n][(1<<m)-1];
}
int main()
{
while(cin>>n>>m)
{
cout<<start()<<endl;
}
return 0;
}
分享到:
相关推荐
SGU 385,我写的程序,一道DP题,跟概率有关
SGU推荐题目分类,适合初次使用sgu的编程爱好者使用!
SGU 390 AC源码,数位统计的难题
SGU题库整合 Volume (200 - 299) pdf版
辛苦整理所得,分略多,绝对值得,sgu完整题库(530个网页,还有试题难度排序)。lnddszp[at]gmail[dot]com
SGU离线题库(2015-6-8整理),图片可以显示。。
sgu oj上的 101-121 的AC代码
SGU-801综合通讯接入装置使用说明书
SGU 103AC 代码 质量有保证!
SGU 333 集训队AC程序,秒过,CPP
sgu ##这是一个将我的 sol 问题存储到 acm.sgu.ru 的存储库
SGU题库 Volume (100-199) pdf整合版
pku sgu 经典图论题解答, 多种方法解答经典图论题, 附源代码
ID 标题 交流电 A + B 18881 互质 7697 第3分部 6906 总和 6185 日历 4336 画线 4159 987654321问题 4014 肉饼 3998 几乎素数 3845 a ^ b-b ^ a 3673 骨牌 3621 花小店 3417 ...1884
Some solution of problems in SPOJ, all of them use DP technique to attack the problems.
sgu176 有源汇的上下界 求最小满足的流 poj 2230 递归求欧拉回路 poj 2985 bst模板 poj2723 2-sat验证,二分答案 poj2455 dinic (ek会超时) hdu1689 求最小奇数环 poj2391 isap最快,dinic不减枝会超时 poj2455 ...
下载调度程序,用于低带宽环境。 全天扩展下载量
“#babylonjs-sgu”
HJVXJVHSKVH JHDK JH DFKSDYFS DVJDSVXCVXCVZXCVZXCV
SGU-用于搜索github用户的输入表单- 描述 您可以通过输入一些文本来找到github用户。 然后,您将拥有一个用户名和用户图标。 仅显示搜索关键字和用户名之间的数据。 库版本 下一个v10.0.7 Reactv17.0.1 react-dom ...