题意
构造方案。满足字典序小的权值一定大。
Solution:
考点：数学+搜索+找规律/推式子。
算法一.
性质一: 对于任意 (i,j) 满足 b[i][j]<=b[i-1][j+1], 因为只有这样才不会出现交叉的情况。该条件对于 n=2 是充要条件，加上爆搜可以得到 45pts
性质二：对于 n=3 打表可以发现下列数据：
0 0 0
0 0 1
0 0 0
观察得到 a[0][1]=a[1][0] ,但是会出现交叉情况，此时要求以 (i,j+1) 为左上角的对角线值相等，结合性质一剪枝可以得到 n,m<=8 的方案数，得分 65pts
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=1e9+7;
int n,m,cnt,b[15][15];
bool vis[15][1000005];
int ans[15][15];
ll res;
bool check2(int x,int y){
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
vis[i][j]=0;
}
}
int x2,y2;
for(int i=0;i<x;i++) {
for(int j=0;j<y;j++) {
if(vis[i][j]) continue;
for(x2=i,y2=j;x2 < x && y2 >= 0 && !vis[x2][y2];x2++,y2--) {
if(b[x2][y2]!=b[i][j]) return 0;
vis[x2][y2]=1;
}
}
}
return 1;
}
void dfs1(int i,int j) {
if(j==m) i++,j=0;
if(i==n) {
res++;
return;
}
for(int k=0;k<2;k++) {
b[i][j]=k;
if(i-1 >= 0 && j + 1 < m && (b[i][j] > b[i-1][j+1] || b[i][j] == b[i-1][j+1] && ! check2(i, j+1))) {
continue;
}
dfs1(i,j+1);
}
}
int main() {
scanf("%d%d",&n,&m); if(n>m) swap(n,m);
ans[8][8]=3626752;
ans[7][8]=ans[8][7]=1360128;
if(n<=8&&m<=8) {
if(ans[n][m]) {
printf("%d",ans[n][m]);
}
else {
dfs1(0,0);
printf("%lld",res);
}
return 0;
}
int x,y; res=1;
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
if(vis[i][j]) continue;
for(x=i,y=j,cnt=0;!vis[x][y] && x<= n && y >= 1;x++,y--) cnt++,vis[x][y]=1;
res=res*(cnt+1)%mod;
}
}
printf("%lld",res);
}
算法二.
考虑 n=3 的情况，观察下列数列：
8 36 112 336 1008 3024 9072 27216 81648 244944 ...
观察到从第 3 项开始公比为 3 ，所以直接输出 f[3] * 3^{m-n} ，得分 80pts
算法三.
考虑 n=4 的情况：
16 108 336 912 2688 8064 24192 72576 217728 653184
观察到从第 5 项开始公比为 3 。
考虑 n=5 的情况：
32 324 1008 2688 7136 21312 63936 191808 575424 1726272
观察到从第 6 项开始公比为 3 。
所以 f_{n,m}=f_{n}*3^(m-n-1),m>=n+1 ，得分 100pts
算法四.
还是考虑 状压 dp 。注意到 (i,j) 满足 性质2 当且仅当：
b[i][j-1]=b[i-1][j](i,j-1) 和 (i-1,j) 满足 性质2
设 dp{i,S} 表示处理了前 i 条斜线，满足性质 2 的集合为 S 的方案数。对于每一个斜线，枚举分界点然后转移，时间复杂度 O(8^{n-2}logm) 。
总结：计数类问题的一般解决思路是打表，然后输出方案，从中得到 重要性质 ，不断修正方案。可以考虑 dp 。
|