hihoCoder 1124-好矩阵 #1124 : 好矩阵 时间限制:3000ms 单点时限:1000ms 内存限制:256MB 描述 给定n, m。一个n × m矩阵是好矩阵当且仅当它的每个位置都是非负整数，且每行每列的和 ≤ 2。求好矩阵的个数，模$$10^9$$ + 7 输入 第一行一个整数T，表示测试点个数。下面T个测试点。每个测试点一行，包含两个整数n，m。1 ≤ T ≤ $$10^4$$. 1 ≤ n, m ≤ 100. 输出 T行。每行是对应测试点的答案。 样例输入 1 2 2 样例输出 26
这一题的题意也很明确，如果是单个测试数据，可以考虑用DFS，但是本题测试数据最多有$$10^4$$，当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。]]>