【题目分析】

沉迷水题,吃枣药丸。

【代码】

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define F(i,j,k) for (int i=j;i<=k;++i)
#define ll long long
int cot[512],c1[512],c2[512][512],n,p;
ll dp[10][512][90];
void print(int x)
{
F(i,0,n-1) printf("%d",(x>>i)&1);
}
void init()
{
F(i,0,(1<<n)-1)
{
int x=i,ret=0;
while (x) ret+=x&1,x>>=1;
cot[i]=ret;
}
F(i,0,(1<<n)-1)
if ((!((i>>1)&i))&&(!((i<<1)&i))) c1[i]=1;
F(i,0,(1<<n)-1) if (c1[i])
F(j,0,(1<<n)-1) if (c1[j])
if ((!((j>>1)&i))&&(!((j<<1)&i))&&(!(j&i)))
{
// print(i); printf("---> "); print(j); printf("\n");
c2[i][j]=1;
}
}
int main()
{
scanf("%d%d",&n,&p);
init();
F(i,0,(1<<n)-1) if (c1[i]) dp[1][i][cot[i]]=1;
F(i,1,n-1) F(j,0,(1<<n)-1)
F(k,0,p) F(l,0,(1<<n)-1)
if (c2[j][l])
{
// printf("dp[%d] ",i+1); print(l); printf(" %d += dp[%d] ",k+cot[l],i); print(j); printf(" %d = %d\n",k,dp[i][j][k]);
dp[i+1][l][k+cot[l]]+=dp[i][j][k];
}
ll ans=0;
F(i,0,(1<<n)-1) ans+=dp[n][i][p];
printf("%lld\n",ans);
}

  

最新文章

  1. 浅析word-break work-wrap区别
  2. jsp xml servlet
  3. [转]angularjs 设置全局变量的3种方法
  4. .NET中的视图和过滤器 (DefaultView和RowFilter)
  5. OSGI.NET 插件无法启动之情景一
  6. css3 --- 翻页动画 --- javascript --- 3d --- Action
  7. Apache Httpd通过mod_jk连接多个Tomcat
  8. 无法为请求的 Configuration 对象创建配置文件 错误原因
  9. android NDK 笔记
  10. js 中对象属性特性的描述
  11. 我的sublime常用快捷键
  12. DWZ在APS.NET WebForm中的使用(二)
  13. SQL 把表中字段存储的逗号隔开内容转换成列表形式
  14. wmic应用实例
  15. vue-cli webpack配置 简单分析
  16. UTF-8的BOM含义
  17. CocosCreator编辑器脚本生命周期函数
  18. talk 1
  19. ubuntu 16.04 静态ip的配置
  20. Oracle_SQL(6) 单行函数

热门文章

  1. Azure 项目构建 – 构建和部署 .NET 应用程序
  2. ubuntu 14.04 离线部署docker
  3. openstack v3 rest 访问
  4. Example of how to implement a view-based source list (NSOutlineView) using Cocoa Bindings
  5. 【Qt】2.2 继续了解信号和槽
  6. myeclipse 导入项目时no projects are found to import解决办法
  7. 几句话总结一个算法之RNN、LSTM和GRU
  8. Arch Linux 天坑
  9. GIMP做成颜色蒙板
  10. Ubuntu中安装配置 JDK与apache