hihocoder 1124 : 好矩阵 dp
好矩阵
描写叙述
给定n, m。一个n × m矩阵是好矩阵当且仅当它的每一个位置都是非负整数,且每行每列的和 ≤ 2。求好矩阵的个数。模109 + 7
输入
第一行一个整数T,表示測试点个数。
以下T个測试点。
每一个測试点一行。包括两个整数n。m。
1 ≤ T ≤ 104. 1 ≤ n, m ≤ 100.
输出
T行。
每行是相应測试点的答案。
例子输入
1
2 2
例子输出
26
题意非常easy。因为,数量非常大。假设考虑一个一个方格的放,要考虑横向的,又要考虑竖向的,非常复杂,所以不可取。所以一排一排的放,假设,m是一定的,那么。每一排仅仅须要考虑不超过2,且与前面已经排好的不冲突就能够了。
dp[i][a][b]表示,第i排,有a列0,b列1,m - a - b列2,的个数则
dp[i+1][a][b]+= dp[i][a][b];//第i+1排全放0
dp[i+1][a-1][b] += (ll)a * dp[i][a][b];//第i+1排在和为0那些列放一个2
dp[i+1][a-1][b+1] += (ll)a * dp[i][a][b];//第i+1排和为1放一个1
dp[i+1][a-1][b]+= (ll)a * (ll) b * dp[i][a][b];//第i+1排和为0 和为1的列各选一个 放两个1
dp[i+1][a][b-1] += (ll)b * dp[i][a][b];//第i+1排选一个和为1的列放一个1
dp[i+1][a-2][b+2] += (ll)(a * (a-1)/2) * dp[i][a][b];//第i+1排选两个和为0放两个1
dp[i+1][a][b-2] += (ll)(b * (b-1)/2) * dp[i][a][b];//第i+1排选两个和为1的放两个1
总复杂度为o(n^4);
#define N 105
#define M 100005
#define maxn 205
#define MOD 1000000007
int n,m,T;
ll dp[N][N][N],ans[N][N];
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
for(int m = 1;m<=100;m++){
int n = 100;
for(int i =0;i<=n;i++){
for(int a = 0;a<=m;a++){
for(int b = 0;b<=m;b++){
dp[i][a][b] = 0;
}
}
}
dp[0][m][0] = 1;
for(int i = 0;i<n;i++){
for(int a = 0;a<=m;a++){
for(int b = 0;a + b<=m;b++){
dp[i+1][a][b]+= dp[i][a][b];
dp[i+1][a][b] %= MOD;
if(a >= 1){
dp[i+1][a-1][b] += (ll)a * dp[i][a][b];
dp[i+1][a-1][b] %= MOD;
dp[i+1][a-1][b+1] += (ll)a * dp[i][a][b];
dp[i+1][a-1][b+1] %= MOD;
}
if(a >= 1 && b >= 1){
dp[i+1][a-1][b]+= (ll)a * (ll) b * dp[i][a][b];
dp[i+1][a-1][b] %= MOD;
}
if(b >= 1 ){
dp[i+1][a][b-1] += (ll)b * dp[i][a][b];
dp[i+1][a][b-1] %= MOD;
}
if(a >= 2 ){
dp[i+1][a-2][b+2] += (ll)(a * (a-1)/2) * dp[i][a][b];
dp[i+1][a-2][b+2] %= MOD;
}
if(b >= 2 ){
dp[i+1][a][b-2] += (ll)(b * (b-1)/2) * dp[i][a][b];
dp[i+1][a][b-2] %= MOD;
}
}
}
ans[i+1][m] = 0;
for(int a = 0;a<=m;a++){
for(int b = 0;b<=m;b++){
ans[i+1][m] += dp[i+1][a][b];
ans[i+1][m] %= MOD;
}
}
}
}
while(S(T)!=EOF)
{
while(T--){
int s,e;
S2(s,e);
printf("%lld\n",ans[s][e]);
}
}
return 0;
}
最新文章
- 64位主机64位oracle下装32位客户端ODAC(NFPACS版)
- java httpclient cookie
- java-7311练习(下)
- linux创建用户、设置密码、修改用户、删除用户
- ubuntu常见错误--could not get lock /var/lib/dpkg/lock -open
- Nginx负载均衡 后端服务器怎么共享Session 问题
- PHP 操作socket 实现简易聊天室
- Jedis 连接redis超时
- SQL注入常用语句
- URAL 2032 - Conspiracy Theory and Rebranding【本源勾股数组】
- HTML5 音频视频
- 不用分支语句实现1+2+。。。+n
- maven settings 配置文件
- AS 400 常用命令
- JAVA 变量 数据类型 运算符 知识小结
- TopCoder SRM502 Div1 1000 动态规划
- Spring与线程安全
- CentOS 7通过RVM来安装指定版本的Ruby
- python第十四课--排序及自定义函数之自定义函数(案例一)
- 在Android中调用KSOAP2库访问webservice服务出现的服务端传入参数为null的问题解决