BZOJ1801 [Ahoi2009]chess 中国象棋(DP, 计数)

时间:2021-10-03 06:54:22

题目链接 [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, 计数)的更多相关文章

  1. bzoj1801&colon; &lbrack;Ahoi2009&rsqb;chess 中国象棋 dp

    题意:在N行M列的棋盘上,放若干个炮可以是0个,使得没有任何一个炮可以攻击另一个炮. 请问有多少种放置方法,中国像棋中炮的行走方式大家应该很清楚吧. 题解:dp[i][j][k]表示到了第i行,有j列 ...

  2. BZOJ1801 Ahoi2009 chess 中国象棋 【DP&plus;组合计数】&ast;

    BZOJ1801 Ahoi2009 chess 中国象棋 Description 在N行M列的棋盘上,放若干个炮可以是0个,使得没有任何一个炮可以攻击另一个炮. 请问有多少种放置方法,中国像棋中炮的行 ...

  3. 【BZOJ1801】&lbrack;Ahoi2009&rsqb;chess 中国象棋 DP

    [BZOJ1801][Ahoi2009]chess 中国象棋 Description 在N行M列的棋盘上,放若干个炮可以是0个,使得没有任何一个炮可以攻击另一个炮. 请问有多少种放置方法,中国像棋中炮 ...

  4. bzoj1801&colon; &lbrack;Ahoi2009&rsqb;chess 中国象棋(DP)

    1801: [Ahoi2009]chess 中国象棋 题目:传送门 题解: 表示自己的DP菜的抠脚 %题解... 定义f[i][j][k]表示前i行 仅有一个棋子的有j列 有两个棋子的有k个 的方案数 ...

  5. BZOJ 1801&colon; &lbrack;Ahoi2009&rsqb;chess 中国象棋&lpar; dp &rpar;

    dp(i, j, k)表示考虑了前i行, 放了0个炮的有j列, 放了1个炮的有k列. 时间复杂度O(NM^2) -------------------------------------------- ...

  6. &lbrack;luogu2051&rsqb;&lbrack;bzoj1801&rsqb;&lbrack;AHOI2009&rsqb;chess中国象棋【动态规划】

    题目描述 这次小可可想解决的难题和中国象棋有关,在一个N行M列的棋盘上,让你放若干个炮(可以是0个),使得没有一个炮可以攻击到另一个炮,请问有多少种放置方法.大家肯定很清楚,在中国象棋中炮的行走方式是 ...

  7. BZOJ1801 &lbrack;Ahoi2009&rsqb;chess 中国象棋 【dp】

    题目 在N行M列的棋盘上,放若干个炮可以是0个,使得没有任何一个炮可以攻击另一个炮. 请问有多少种放置方法,中国像棋中炮的行走方式大家应该很清楚吧. 输入格式 一行包含两个整数N,M,中间用空格分开. ...

  8. BZOJ 1801&colon; &lbrack;Ahoi2009&rsqb;chess 中国象棋 &lbrack;DP 组合计数&rsqb;

    http://www.lydsy.com/JudgeOnline/problem.php?id=1801 在N行M列的棋盘上,放若干个炮可以是0个,使得没有任何一个炮可以攻击另一个炮. 请问有多少种放 ...

  9. BZOJ1801 &lbrack;Ahoi2009&rsqb;chess 中国象棋 动态规划

    欢迎访问~原文出处——博客园-zhouzhendong 去博客园看该题解 题目传送门 - BZOJ1801 题意概括 在N行M列的棋盘上,放若干个炮可以是0个,使得没有任何一个炮可以攻击另一个炮. 请 ...

随机推荐

  1. SpringMVC学习系列-后记 解决GET请求时中文乱码的问题

    SpringMVC学习系列-后记 解决GET请求时中文乱码的问题 之前项目中的web.xml中的编码设置: <filter> <filter-name>CharacterEnc ...

  2. 使用Python 将shapefile导入mongodb

    使用Python 将shapefile导入mongodb 随着big data时代的到来,各个行业都在考虑能不能把big data的思路.方法引入进来,GIS行业也不能免俗. 下面就介绍一下如何将sh ...

  3. hiho一下 第九十四周 数论三&&num;183&semi;约瑟夫问题

    数论三·约瑟夫问题 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 小Hi和小Ho的班级正在进行班长的选举,他们决定通过一种特殊的方式来选择班长. 首先N个候选人围成一个 ...

  4. 转--Android如何在java代码中设置margin

    ========  3 在Java代码里设置button的margin(外边距)? 1.获取按钮的LayoutParams LinearLayout.LayoutParams layoutParams ...

  5. 项目架构开发:数据访问层之Repository

    接上文 项目架构开发:数据访问层之Logger 本章我们继续IRepository开发,这个仓储与领域模式里边的仓储有区别,更像一个工具类,也就是有些园友说的“伪仓储”, 这个仓储只实现单表的CURD ...

  6. Spring中的Service&sol;DAO&sol;DTO

  7. 【Mac】Mac中如何将相同后缀的所有文件设置指定软件打开

    操作步骤: 以settings.xml文件为例 1.首先选中该文件,鼠标右键打开功能列表,选则查看文件信息 2.在文件信息中,进行相关设置

  8. 第七章 LED将为我闪烁:控制发光二级管

    LED驱动开发实验 如图所示,LED1-LED2 分别与GPC0_3.GPC0_4 相连,通过GPC0_3.GPC0_4 引脚的高低电平来控制三极管的导通性,从而控制LED 的亮灭. 根据三极管的特性 ...

  9. python测试开发django-53&period;xadmin里Model分类管理&lpar;proxy&equals;True&rpar;

    前言 django的xadmin后台使用xadmin.site.register注册时,一张表只能注册一次,在后面页面上只能显示出一个页面. 有时候我们想从里面筛选出自己想要的数据,比如有全部的学生成 ...

  10. div产生的滚动条返回顶部

    div产生的滚动条返回顶部 1.获取div js: let initialNode = document.getElementById("content") react: let ...