hihoCoder 1124-好矩阵
#1124 : 好矩阵
时间限制:3000ms
单点时限:1000ms
内存限制:256MB
描述
给定n, m。一个n × m矩阵是好矩阵当且仅当它的每个位置都是非负整数，且每行每列的和 ≤ 2。求好矩阵的个数，模 + 7
输入
第一行一个整数T，表示测试点个数。下面T个测试点。每个测试点一行，包含两个整数n，m。1 ≤ T ≤ . 1 ≤ n, m ≤ 100.
输出
T行。每行是对应测试点的答案。
样例输入
1
2 2
样例输出
26
这一题的题意也很明确，如果是单个测试数据，可以考虑用DFS，但是本题测试数据最多有，当n和m不同时，DFS的结果不能复用，所以超时妥妥的。
要想中间结果复用，一定是DP，所以考虑用DP来做，我是参考了
题解和
此博客。
完整代码如下：
[cpp]
#include<iostream>
#include<cstdio>
using namespace std;
const int kMaxMN = 105, kMod = 1000000007;
typedef long long ll;
ll f[kMaxMN][kMaxMN][kMaxMN];
ll ans[kMaxMN][kMaxMN];
void Init()
{
for (int m = 1; m < kMaxMN; m++)
{
for (int n = 0; n < kMaxMN; n++)
for (int a = 0; a <= m; a++)
for (int b = 0; a + b <= m; b++)
f[n][a][b] = 0;
f[0][m][0] = 1;
for (int n = 1; n < kMaxMN; n++)
{
//f[n][m][0] = 1;//如果f[n-1][m][0]=0，即不存在全为0的情况，则f[n][m][0]不等于1而是等于0
for (int a = 0; a <= m; a++)
{
for (int b = 0; a + b <= m; b++) { f[n][a][b] += f[n – 1][a][b];//(1) f[n][a][b] %= kMod; if (a > 0)
{
//(2.1)
f[n][a – 1][b + 1] += (ll)a*f[n – 1][a][b];
f[n][a – 1][b + 1] %= kMod;
//(4)
f[n][a – 1][b] += (ll)a*f[n – 1][a][b];
f[n][a – 1][b] %= kMod;
}
if (b > 0)//(2.2)
{
f[n][a][b – 1] += (ll)b*f[n – 1][a][b];
f[n][a][b – 1] %= kMod;
}
if (a > 1)//3.1
{
f[n][a – 2][b + 2] += (ll)(a*(a – 1) / 2)*f[n – 1][a][b];
f[n][a – 2][b + 2] %= kMod;
}
if (a > 0 && b > 0)//3.2
{
f[n][a – 1][b] += (ll)a*(ll)b*f[n – 1][a][b];
f[n][a – 1][b] %= kMod;
}
if (b > 1)//3.3
{
f[n][a][b – 2] += (ll)(b*(b – 1) / 2)*f[n – 1][a][b];
f[n][a][b – 2] %= kMod;
}
}
}
ans[n][m] = 0;
for (int a = 0; a <= m; a++)
{
for (int b = 0; a + b <= m; b++)
{
ans[n][m] += f[n][a][b];
ans[n][m] %= kMod;
}
}
}
}
}
int main()
{
Init();
int t,n,m;
scanf("%d", &t);
while (t–)
{
scanf("%d %d", &n, &m);
printf("%lldn", ans[n][m]);
}
return 0;
}
[/cpp]
转换情况较多，代码和题解对照查看。
本代码提交AC，用时1698MS，内存9MB。]]>