题目链接 [Ahoi2009]chess 中国象棋
设$f[i][j][k]$为前i行,$j$列放了1个棋子,$k$列放了2个棋子的方案数
分6种情况讨论,依次状态转移。
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i) typedef long long LL;
const LL mod = ;
int n, m;
LL f[][][], ans = ; inline LL calc(LL x){ return x * (x - ) / ;} int main(){ scanf("%d%d", &n, &m);
f[][][] = ;
rep(i, , n){ rep(j, , m){ rep(k, , m - j){
f[i][j][k] = f[i - ][j][k];
if (j) f[i][j][k] += f[i - ][j - ][k] * (m - k - j + );
if (j < m && k) f[i][j][k] += f[i - ][j + ][k - ] * (j + );
if (j && k) f[i][j][k] += f[i - ][j][k -] * j * (m - j - k + );
if (j > ) f[i][j][k] += f[i - ][j - ][k] * calc(m - k - j + );
if (j <= m - && k > ) f[i][j][k] += f[i - ][j + ][k - ] * calc(j + );
f[i][j][k] %= mod;
} }
} rep(i, , m) rep(j, , m - i) (ans += f[n][i][j]) %= mod;
printf("%lld\n", ans);
return ;
}
BZOJ1801 [Ahoi2009]chess 中国象棋(DP, 计数)的更多相关文章
-
bzoj1801: [Ahoi2009]chess 中国象棋 dp
题意:在N行M列的棋盘上,放若干个炮可以是0个,使得没有任何一个炮可以攻击另一个炮. 请问有多少种放置方法,中国像棋中炮的行走方式大家应该很清楚吧. 题解:dp[i][j][k]表示到了第i行,有j列 ...
-
BZOJ1801 Ahoi2009 chess 中国象棋 【DP+组合计数】*
BZOJ1801 Ahoi2009 chess 中国象棋 Description 在N行M列的棋盘上,放若干个炮可以是0个,使得没有任何一个炮可以攻击另一个炮. 请问有多少种放置方法,中国像棋中炮的行 ...
-
【BZOJ1801】[Ahoi2009]chess 中国象棋 DP
[BZOJ1801][Ahoi2009]chess 中国象棋 Description 在N行M列的棋盘上,放若干个炮可以是0个,使得没有任何一个炮可以攻击另一个炮. 请问有多少种放置方法,中国像棋中炮 ...
-
bzoj1801: [Ahoi2009]chess 中国象棋(DP)
1801: [Ahoi2009]chess 中国象棋 题目:传送门 题解: 表示自己的DP菜的抠脚 %题解... 定义f[i][j][k]表示前i行 仅有一个棋子的有j列 有两个棋子的有k个 的方案数 ...
-
BZOJ 1801: [Ahoi2009]chess 中国象棋( dp )
dp(i, j, k)表示考虑了前i行, 放了0个炮的有j列, 放了1个炮的有k列. 时间复杂度O(NM^2) -------------------------------------------- ...
-
[luogu2051][bzoj1801][AHOI2009]chess中国象棋【动态规划】
题目描述 这次小可可想解决的难题和中国象棋有关,在一个N行M列的棋盘上,让你放若干个炮(可以是0个),使得没有一个炮可以攻击到另一个炮,请问有多少种放置方法.大家肯定很清楚,在中国象棋中炮的行走方式是 ...
-
BZOJ1801 [Ahoi2009]chess 中国象棋 【dp】
题目 在N行M列的棋盘上,放若干个炮可以是0个,使得没有任何一个炮可以攻击另一个炮. 请问有多少种放置方法,中国像棋中炮的行走方式大家应该很清楚吧. 输入格式 一行包含两个整数N,M,中间用空格分开. ...
-
BZOJ 1801: [Ahoi2009]chess 中国象棋 [DP 组合计数]
http://www.lydsy.com/JudgeOnline/problem.php?id=1801 在N行M列的棋盘上,放若干个炮可以是0个,使得没有任何一个炮可以攻击另一个炮. 请问有多少种放 ...
-
BZOJ1801 [Ahoi2009]chess 中国象棋 动态规划
欢迎访问~原文出处——博客园-zhouzhendong 去博客园看该题解 题目传送门 - BZOJ1801 题意概括 在N行M列的棋盘上,放若干个炮可以是0个,使得没有任何一个炮可以攻击另一个炮. 请 ...
随机推荐
-
SpringMVC学习系列-后记 解决GET请求时中文乱码的问题
SpringMVC学习系列-后记 解决GET请求时中文乱码的问题 之前项目中的web.xml中的编码设置: <filter> <filter-name>CharacterEnc ...
-
使用Python 将shapefile导入mongodb
使用Python 将shapefile导入mongodb 随着big data时代的到来,各个行业都在考虑能不能把big data的思路.方法引入进来,GIS行业也不能免俗. 下面就介绍一下如何将sh ...
-
hiho一下 第九十四周 数论三&#183;约瑟夫问题
数论三·约瑟夫问题 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 小Hi和小Ho的班级正在进行班长的选举,他们决定通过一种特殊的方式来选择班长. 首先N个候选人围成一个 ...
-
转--Android如何在java代码中设置margin
======== 3 在Java代码里设置button的margin(外边距)? 1.获取按钮的LayoutParams LinearLayout.LayoutParams layoutParams ...
-
项目架构开发:数据访问层之Repository
接上文 项目架构开发:数据访问层之Logger 本章我们继续IRepository开发,这个仓储与领域模式里边的仓储有区别,更像一个工具类,也就是有些园友说的“伪仓储”, 这个仓储只实现单表的CURD ...
- Spring中的Service/DAO/DTO
-
【Mac】Mac中如何将相同后缀的所有文件设置指定软件打开
操作步骤: 以settings.xml文件为例 1.首先选中该文件,鼠标右键打开功能列表,选则查看文件信息 2.在文件信息中,进行相关设置
-
第七章 LED将为我闪烁:控制发光二级管
LED驱动开发实验 如图所示,LED1-LED2 分别与GPC0_3.GPC0_4 相连,通过GPC0_3.GPC0_4 引脚的高低电平来控制三极管的导通性,从而控制LED 的亮灭. 根据三极管的特性 ...
-
python测试开发django-53.xadmin里Model分类管理(proxy=True)
前言 django的xadmin后台使用xadmin.site.register注册时,一张表只能注册一次,在后面页面上只能显示出一个页面. 有时候我们想从里面筛选出自己想要的数据,比如有全部的学生成 ...
-
div产生的滚动条返回顶部
div产生的滚动条返回顶部 1.获取div js: let initialNode = document.getElementById("content") react: let ...