题目：?1287: B304
参考：?WUST OJ 1287：B304（DP）——Mitsuha_
题目?
有一间教室，里面有N行M列桌子（N和M键盘输入）每个桌子上最多有一朵?（0朵花或者1朵花），?的总数量不限每行和每列的?的数量都只能为奇数最多有100行100列桌子问题：有N行M列桌子，?的摆放方法有多少种？
分析
感谢参考博客，因为我是直接拿参考博客的代码运行，通过大量数据总结的规律。 实际上，这种题做的少的话，不容易找到规律（不信可以试试?）。
?画表格分析（带下划线的数据是?参考博客代码运行出来的，如果你能算出来，评论区讨论✒️，给你点赞?表示佩服）
N \ M1234561101010202080323101602560408051203276851025606553606032032768033554432
最先想到的应该是对称矩阵，因此代码中，我们只需要初始化右上三角部分即可（注：文末有思考题，看完再思考。）其次，可以发现规律：N和M奇偶性不同的时候，方法种数必为0。（能手画总结出来）
看完表格可能就发现所有的数都是2n（n为自然数）的形式，n的取值情况如?，不考虑上面表格中值为0的情况，不考虑左下三角的情况：
N \ M123456100021353484915516625
可以看（连猜带蒙）出
第
1行的公差d1为
2 * (1 - 1)
第
2行的公差d2为
2 * (2 - 1)
第
3行的公差d3为
2 * (3 - 1)，待验证
第
4行的公差d4为
2 * (4 - 1)，待验证
...
第i行的公差di为
2 * (i
- 1)
...
递推公式：di = 2 * (i - 1)
你会想，要是不同行之间也有规律就好了。你别说还真有，请看对角线数据，注：第1个1是初始化的，不在表格中
0 = 1 + 2 * (1 - 1) - 1
1 = 0 + 2 * (2 - 1) - 1
4 = 1 + 2 * (3 - 1) - 1
9 = 4 + 2 * (4 - 1) - 1
16 = 9 + 2 * (5 - 1) - 1
25 = 16 + 2 * (6 - 1) - 1
由于di
= 2 * (i
- 1)，故
0 = 1 + d1
- 1
1 = 0 + d2
- 1
4 = 1 + d3
- 1
9 = 4 + d4
- 1
16 = 9 + d5
- 1
25 = 16 + d6
- 1
递推公式：an = an-1 + dn - 1 递推公式都有了，现在代码写起来简单了吧！
Java
import java
.util
.Scanner
;
public class Main {
private static final int MOD
= 1000000007;
private static final int MAX_NM
= 101;
private int[][] ways
;
public Main() {
init();
int m
, n
;
Scanner sc
= new Scanner(System
.in
);
while (sc
.hasNext()) {
n
= sc
.nextInt();
m
= sc
.nextInt();
if (n
< m
) {
System
.out
.println(ways
[n
][m
]);
} else {
System
.out
.println(ways
[m
][n
]);
}
}
sc
.close();
}
private void init() {
ways
= new int[MAX_NM
][MAX_NM
];
int diagonal
= 1;
int d
;
for (int i
= 1; i
< MAX_NM
; i
++) {
d
= 2 * (i
- 1);
diagonal
+= d
- 1;
ways
[i
][i
] = 1;
for (int j
= 0; j
< diagonal
; j
++) {
ways
[i
][i
] = (ways
[i
][i
] << 1) % MOD
;
}
for (int j
= i
+ 2; j
< MAX_NM
; j
+= 2) {
ways
[i
][j
] = ways
[i
][j
- 2];
for (int k
= 0; k
< d
; k
++) {
ways
[i
][j
] = (ways
[i
][j
] << 1) % MOD
;
}
}
}
}
public static void main(String
[] args
) {
new Main();
}
}
C（注释见Java版）
#include<stdio.h>
#define MAX_NM 101
#define MOD 1000000007
int ways
[MAX_NM
][MAX_NM
];
void init() {
int diagonal
= 1;
int d
;
for (int i
= 1; i
< MAX_NM
; i
++) {
d
= 2 * (i
- 1);
diagonal
+= d
- 1;
ways
[i
][i
] = 1;
for (int j
= 0; j
< diagonal
; j
++) {
ways
[i
][i
] = (ways
[i
][i
] << 1) % MOD
;
}
for (int j
= i
+ 2; j
< MAX_NM
; j
+= 2) {
ways
[i
][j
] = ways
[i
][j
- 2];
for (int k
= 0; k
< d
; k
++) {
ways
[i
][j
] = (ways
[i
][j
] << 1) % MOD
;
}
}
}
}
int main() {
init();
int m
, n
;
while (scanf("%d%d", &n
, &m
) != EOF) {
if (n
< m
) {
printf("%d\n", ways
[n
][m
]);
}
else {
printf("%d\n", ways
[m
][n
]);
}
}
return 0;
}
注释如此详细，应该能看懂吧！ 思考题：为什么初始化右上角部分，而不是左下角部分？（大佬跳过） 答：现在假设你的程序已经计算出了第一个数[1][1]，因此题目演变成你现在要计算[1][3]还是[3][1]的问题？很明显，计算[1][3]只需要移动1位，而计算[3][1]需要移动12位，其他数据同理，前者块，后者慢。 结论：访问二维数组的时候，尽量将移动距离大的（一维）放在外层循环，移动距离小的（二维）放在内层循环。不仅限于此，其他地方也可以这么思考。
如有帮助，还望?支持，谢谢！
备注：第一次发现可以贴表情，所以用的有点多，见谅！
版权声明：
转载请于首页注明链接形式的WUSTOJ 1287: B304（Java）——wowpH；代码原创，公开引用不能删除首行注释（作者，版本号，时间等信息）；如果有疑问欢迎评论区留言，尽量解答；如果有错误，还望大侠评论区指正。
