BZOJ1801 Ahoi2009 chess 中国象棋 【DP+组合计数】*
2024-10-10 23:38:35
BZOJ1801 Ahoi2009 chess 中国象棋
Description
在N行M列的棋盘上,放若干个炮可以是0个,使得没有任何一个炮可以攻击另一个炮。 请问有多少种放置方法,中国像棋中炮的行走方式大家应该很清楚吧.
Input
一行包含两个整数N,M,中间用空格分开.
Output
输出所有的方案数,由于值比较大,输出其mod 9999973
Sample Input
1 3
Sample Output
7
HINT
除了在3个格子中都放满炮的的情况外,其它的都可以.
100%的数据中N,M不超过100
50%的数据中,N,M至少有一个数不超过8
30%的数据中,N,M均不超过6
不难发现每行每列最多只有2个棋子
考虑DP,dpi,j,kdp_{i,j,k}dpi,j,k表示i行中一共有j列有一个,k列有两个
然后我们考虑这一行选多少
- 当前行不选
dpi,j,k=dpi−1,j,k - 当前行选一个
- 选原来是0个棋子dp(i,j,k)+=dp(i−1,j−1,k)∗c(n−k−j+1,1)(1≤j)
- 选原来是1个棋子dp(i,j,k)+=dp(i−1,j+1,k−1)∗c(j+1,1)(1≤k,j≤m−1)
- 当前行选两个
- 选两个原来是0的dp(i,j,k)+=dp(i−1,j−2,k)*c(m-j-k+1,2)(2≤j)
- 选两个原来是1的dp(i,j,k)+=dp(i−1,j+2,k−2)*c(j+2,2)(2≤k,j≤m−2)
- 选一个是1一个是0 dp(i,j,k)+=dp(i−1,j,k−1)*j*(m-j-k+1)(1≤j,1≤k(要保证原来有1))
然后就可以进行转移了
#include<bits/stdc++.h>
using namespace std;
#define fu(a,b,c) for(int a=b;a<=c;++a)
#define fd(a,b,c) for(int a=b;a>=c;--a)
#define N 110
#define LL long long
#define Mod 9999973
LL c[N][N];
LL dp[N][N][N]={};
int n,m;
void getc(){
fu(i,,N-)c[i][]=;
fu(i,,N-)
fu(j,,i)c[i][j]=(c[i-][j]+c[i-][j-])%Mod;
}
LL mul(LL a,LL b){return a*b%Mod;}
int main(){
getc();
dp[][][]=;
scanf("%d%d",&n,&m);
if(n<m)swap(n,m);
fu(i,,n)
fu(j,,m)
fu(k,,m-j){
dp[i][j][k]=dp[i-][j][k];
if(j)dp[i][j][k]+=mul(dp[i-][j-][k],c[m-j-k+][]);
if(j&&k)dp[i][j][k]+=mul(dp[i-][j][k-],mul(j,m-j-k+));
if(j>=)dp[i][j][k]+=mul(dp[i-][j-][k],c[m-j-k+][]);
if(k>=&&j<=m-)dp[i][j][k]+=mul(dp[i-][j+][k-],c[j+][]);
if(k>=&&j<=m-)dp[i][j][k]+=mul(dp[i-][j+][k-],c[j+][]);
dp[i][j][k]%=Mod;
}
int ans=;
fu(i,,m)
fu(j,,m-i)
ans=(ans+dp[n][i][j])%Mod;
printf("%d",ans);
return ;
}
最新文章
- JS继承之寄生类继承
- 在Activity之间传递参数(四)
- sql server 2005导出数据到oracle
- iOS -- cocopods使用
- mysql dump
- InstallShield 2010 使用 .net framework 4.5
- Android 自定义波浪动画 --";让进度浪起来~";
- 安卓设备通过USB接口读取UVC摄像头权限问题
- Q: How could I use MATLAB interface for parameter selection?
- cpio备份命令
- Java IO (2) - OutputStream
- 中文字符集编码Unicode ,gb2312 , cp936 ,GBK,GB18030
- strcmp函数实现及分析
- URAL1523(dp+树状数组)
- php框架Yaf路由重写
- 网络配置之nmcli
- 阿里云部署Docker(6)----解决删除&;lt;none&;gt;镜像问题
- c#中的Unity容器
- 【代码笔记】iOS-tableView滑动的范围函数
- Delphi: RTTI与ini配置文件
热门文章
- spring 及 spring boot 资源文件配置
- hdu 4857 逃生 拓扑排序+逆向建图
- pg按日,周,月进行数据统计
- Python 的selenium使用
- PIL中文文档
- MS SQL2008执行大脚本文件时,提示“内存不足”的解决办法
- cJSON序列化工具解读一(结构剖析)
- 阅读《大型网站技术架构:核心原理与案例分析》第五、六、七章,结合《XXX重大技术需求征集系统》,列举实例分析采用的可用性和可修改性战术,将上述内容撰写成一篇1500字左右的博客阐述你的观点。
- JAVA之Map使用
- [Web UI]对比Angular/jQueryUI/Extjs:没有一个框架是万能的