题目:https://www.lydsy.com/JudgeOnline/problem.php?id=4806

看到这题首先会想到状压什么乱七八糟的,然而很难做;

其实,因为求的是方案数,所以并不需要关注炮摆放的位置,而只需要关注数量;

f[i][j][k] 表示第 i 行及以前共有 j 个有 0 炮的列和 k 个有 1 炮的列,就可以转移了。

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
int const mod=,maxn=;
ll n,m,f[maxn][maxn][maxn],ans;
ll C(ll x){return ((x-)*x/)%mod;}//不是(x+1) !!
int main()
{
scanf("%d%d",&n,&m);
f[][m][]=;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)//
for(int k=;k<=m-j;k++)//
{
(f[i][j][k]+=f[i-][j][k])%=mod;//放0个
if(k>=&&j<m)(f[i][j][k]+=f[i-][j+][k-]*(j+))%=mod;//0 -> 1 //别写成 if(k&&j<m) !!
if(k<m)(f[i][j][k]+=f[i-][j][k+]*(k+))%=mod;//1 -> 2
if(j<m)(f[i][j][k]+=f[i-][j+][k]*(j+)*k)%=mod;//0 1 -> 1 2
if(k->=&&j+<=m)(f[i][j][k]+=f[i-][j+][k-]*C(j+))%=mod;//0 0 -> 1 1
if(k+<=m)(f[i][j][k]+=f[i-][j][k+]*C(k+))%=mod;//1 1 -> 2 2
}
for(int j=;j<=m;j++)
for(int k=;k<=m;k++)
(ans+=f[n][j][k])%=mod;
printf("%lld",ans);
return ;
}

最新文章

  1. [转]通过Visual Studio为Linux编写C++代码
  2. es let2
  3. Java和C#语法对比
  4. int long 等基础类型在不同平台的大小
  5. Swing开发之JComboBox篇
  6. Hive介绍、安装(转)
  7. 正向代理VS反向代理 总结
  8. 洛谷P2014 TYVJ1051 选课
  9. JAVA 继承 extends
  10. 图片裁切插件jCrop的使用心得(四)
  11. Object.prototype.toString.call() 区分对象类型(判断对象类型)
  12. 吞吐量(Throughput)、QPS、并发数、响应时间(RT)对系统性能的影响
  13. PRINCE2的国际形势?光环国际项目管理培训
  14. Oracle存储过程经典入门
  15. Ubuntu on win10
  16. underscore.js源码解析【数组】
  17. 2018-2019-2 《网络对抗技术》Exp0 Kali安装 Week1 20165320
  18. Ubuntu下好的PDF阅读器介绍
  19. php正则替换双引号里面的字符
  20. TextView

热门文章

  1. Linux 修改主机名
  2. Linux核心参数Shmmax,shmall,shmni
  3. 前端接收到的json的属性的首字母会自动变成小写,解决办法如下
  4. 匈牙利游戏(codevs 1269)
  5. [NOIP1998] 普及组
  6. POJ3233:Matrix Power Series
  7. httpclient自动执行http的302重定向
  8. 离线配置Anaconda3+tensorflow-gpu1.4.0+cuda8.0+cudnn6.0
  9. QT程序--小工具集合
  10. 拷贝地图 CopyAndOverwriteMap()