BZOJ 1801: [Ahoi2009]chess 中国象棋 [DP 组合计数]
2024-08-26 00:11:13
http://www.lydsy.com/JudgeOnline/problem.php?id=1801
在N行M列的棋盘上,放若干个炮可以是0个,使得没有任何一个炮可以攻击另一个炮。 请问有多少种放置方法
100%的数据中N,M不超过100
容易发现每行每列最多两个
然后就不会了...看了别人的状态表示:
$f[i][j][k]$表示前$i$行有$j$列放了$1$个$k$列放了$2$个
因为只有那些行放了几个影响当前转移
然后转移自己随便写写就行了....注意$j$可能需要减
$1A$啦啦啦
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
using namespace std;
typedef long long ll;
const int N=,P=;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,m;
ll f[N][N][N];
inline int C2(int n){return n*(n-)/;}
void dp(){//printf("dp %d %d\n",m,n);
f[][][]=;
for(int i=;i<m;i++)
for(int j=;j<=n;j++)
for(int k=;k<=n&&n-j-k>=;k++) if(f[i][j][k]){//printf("update %d %d %d\n",i,j,k);
ll now=f[i][j][k];
(f[i+][j][k]+=now)%=P; if(j<n) (f[i+][j+][k]+=now*(n-j-k))%=P;
if(j>=) (f[i+][j-][k+]+=now*j)%=P; if(j+<=n) (f[i+][j+][k]+=now*C2(n-j-k))%=P;
if(j>=&&k+<=n) (f[i+][j-][k+]+=now*C2(j))%=P;
if(k<n) (f[i+][j][k+]+=now*(n-j-k)*j)%=P;
}
//for(int i=0;i<=m;i++) for(int j=0;j<=n;j++) for(int k=0;k<=n;k++) printf("f %d %d %d %lld\n",i,j,k,f[i][j][k]);
ll ans=;
for(int j=;j<=n;j++) for(int k=;k<=n;k++) ans=(ans+f[m][j][k])%P;//printf("hi %d %d %lld\n",j,k,f[m][j][k]);
printf("%lld",ans);
}
int main(){
freopen("in","r",stdin);
m=read();n=read();
if(n>m) swap(m,n);
dp();
}
最新文章
- 1Z0-053 争议题目解析700
- 构建高可用ZooKeeper集群(转载)
- js URL中文传参乱码
- Cookies的作用
- Hadoop配置文件
- 脱离rails 使用Active Record
- 如何用CSS进行开发
- jQuery.inArray 方法的实现
- ASP.NET中的注释 .
- oracle学习之-----操作表中的数据
- Spring AOP实现方式四之注入式AspectJ切面【附源码】
- 1、IIS常见的的问难及解决方法
- [TypeScript] Using Typings and Loading From node_modules
- 每天一个JavaScript实例-动态省份选择城市
- Hive综合HBase——经Hive阅读/书写 HBase桌子
- iOS 错误之 NSObject 、CGFloat
- angularjs初窥门径
- Vue渐进式JavaScript 框架
- 如何在MyBatis中优雅的使用枚举
- Sping Cloud hystrix.stream 自动发现-监控