不妨设 \(n, m\) 相等，常规的状压 DP 做法时间复杂度为 \(O(n * 2^n)\)，但是可以通过套用公式使复杂度变为 \(O(n^2)\)。
具体地，用 \(1*2\) 的小长方形覆盖 \(n*m\) 的棋盘的方案数为
\[\Large \prod\limits_{j = 1}^{\left\lceil\frac{m}{2}\right\rceil} \prod\limits_{k = 1}^{\left\lceil\frac{n}{2}\right\rceil} \left( 4 \cos^2 \frac{\pi j}{m + 1} + 4 \cos^2 \frac{\pi k}{n + 1} \right)
\]
当 \(n\) 和 \(m\) 均为奇数时，上述公式能正确给出答案 \(0\)。
点击查看代码
#include<math.h>
#include<stdio.h>
#include<ctype.h>
#define pi 3.14159265358979323846
int n, m;
long double ans;
int main(){
while(1){
scanf("%d%d", &n, &m);
if(!n) break;
ans = 1;
for(int i = 1; i <= (n + 1) / 2; i++){
for(int j = 1; j <= (m + 1) / 2; j++){
ans *= 4.0 * (cos((pi * i) / (n + 1)) * cos((pi * i) / (n + 1)) + cos((pi * j) / (m + 1)) * cos((pi * j) / (m + 1)));
}
}
printf("%lld\n", (long long)(ans + 0.5));
}
return 0;
}
参考