这是一道 打表\(+\)乱搞 题，目前只会打表和乱搞做法，以后水品提升了不知道能不能作出证明或者写出状压？？
首先我们可以发现 \(n \le 3\) 的情况有 \(65pts\)，而 \(n\) 这么小，打一下表何乐而不为呢？于是我写了一个爆枚每个位置再 \(check\) 的 \(dfs\)，复杂度 \(O(2 ^ {nm + n + m} \log 2 ^ {n + m - 1})\) 因为 \(n\) 实在太小了于是我打出了下面的表（\(1\) 的情况直接算就没打了，下面第一个数都是从 \(m = n\) 开始的）
2 : 12 36 108 324 ...
3 : 112 336 1008 3024 ...
很明显可以发现这里每个答案往后都乘了 \(3\)，于是我们只需要写一个快速幂就可以获得 \(65pts\) 的高分。之后我算出了 \((4, 4)\) 的答案 \(912\)，又算了 \((4, 5)\) 的答案想要验证乘 \(3\) 的猜想，但 \((4, 5)\) 却是 \(2688 \ne 3 \times 912\)，然后我再想跑出 \((4, 6)\) 的答案，可是目前的 \(dfs\) 大概要跑 \(2h\) 左右，于是我再分析了一下样例，发现实际上题目的要求是优先往右走的路径的 \(01\) 字典序要不大于优先往下走的所有路径 \(01\) 字典序，因此我有了这样一个剪枝方法，我们先暴力枚举第一列的所有数，然后从最后一行开始暴力枚举，吧每一条路径压乘十进制数在树状数组上修改，那么再一遍遍爆枚上一层，记录一下每个位置到终点的最大 \(01\) 字典序加到当前的字典序后面然后再在线段树上查询是否有小于当前字典序的串，如果有剪枝即可。这个东西看起来很难实现，而且复杂度也很玄学，回头想一下题目的条件，要求优先往右走的字典序小，那么假设现在有两个 \(01\) 串 \(a, b\) 前者优先往下走，后者优先往右走，假设目前两串相同，如果下面 \(a < b\) 那么后者必然走到 \(1\) 而前者必然走到 \(0\)，再注意到 \(a, b\) 长度应该相等也就意味着两者走的步数相同，那么两者应该都在左下到右上的一条对角线上，因此我们可以得出一个结论，每一条左下到右上的对角线都是先一段 \(1\) 后一段 \(0\)。那么我们就可以有了一种新的爆搜方式，我们爆枚每个对角线 \(0, 1\) 分界点，再暴力 \(check\) 这样复杂度是 \(O((m!) ^ 2 2 ^ {n + m} \log 2 ^ {n + m})\)，算了一下这东西能跑出 \((6, 6)\)，于是我实现了这个 \(dfs\)，发现 \((6, 6)\) 只需要 \(15s\)，于是我让他去跑 \((7, 7)\) 打出了 \(n \le 6\) 的表。
2 : 12 36 108 324 972 2916 ...
3 : 112 336 1008 3024 9072 27216 ...
4 : 912 2688 8064 24192 72576 217728 ...
5 : 7136 21312 63936 191808 ...
6 : 56768 170112 510336 ...
可以发现，虽然 \((4, 4) \rightarrow (4, 5)\) 不是乘 \(3\)，但 \((4, 5) \rightarrow (4, 6), (4, 6) \rightarrow (4, 7)\) 接下来都是乘 \(3\)，对于 \(5, 6\) 也是一样。于是我们大胆地猜测剩下的所有情况应该都是从第二项开始乘 \(3\) 的。那我们只需要求出第一项和第二项即可。
过了 \(20min\) 终于跑出了 \((7, 7)\)，现在的表如下：
2 : 12 36 108 324 972 2916 ...
3 : 112 336 1008 3024 9072 27216 ...
4 : 912 2688 8064 24192 72576 217728 ...
5 : 7136 21312 63936 191808 ...
6 : 56768 170112 510336 ...
7 : 453504 ...
感觉 \((7, 8)\) 应该是死都跑不出来了，但是我们打表出了这么多数据，可以找一下规律。我们发现 \(n \ge 4\) 时虽然第一项乘 \(3\) 不等于第二项，但隔得非常近，于是我算出了 \(n = 4\) 时 \(912 \times 3 - 2688 = 48\)，接着再算了 \(n = 5\) 时 \(7136 \times 3 - 21312 = 96\)，然后又算了 \(n = 6\) 时 \(56768 \times 3 - 170112 = 192\)，规律非常明显了，每次插值乘了 \(2\)，并且可以发现 \(48 = 3 \times 2 ^ 4, 96 = 3 \times 2 ^ 5\)，于是我们可以发现 \((n, n + 1) = 3 \times (n, n) - 3 \times 2 ^ n\)，那么我们只需要跑出 \((8, 8)\) 这题就做完了，然而貌似 \((8, 8)\) 根本跑不出...
应该还有规律，继续观察。可以发现 \(m \ge n + 2\) 的情况都是从 \((n, n + 1)\) 推来的，而 \((n, n + 1)\) 与 \((n, n)\) 有关，于是我们可以考虑只观察前面两项，观察一段时间后可以发现 \(((n, n) + (n, n + 1)) \times 2\) 与 \((n + 1, n + 1)\) 非常接近，于是我又算了他们的差值可以发现 \(4 \rightarrow 5 = 64, 5 \rightarrow 6 = 128, 6 \rightarrow 7 = 256\)，规律也非常明显，每次乘了 \(2\)，并且可以发现每次的插值 \(i - 1 \rightarrow i = 2 ^ {i + 1}\)，那么我们岂不是知道前两项的递推式了？令 \(f_{i, j}\) 为 \((i, j)\) 的答案，于是我们有 \(f_{i, i} = (f_{i - 1, i - 1} + f_{i - 1, i}) \times 2 - 2 ^ {i + 1}, f_{i, i + 1} = 3 \times f_{i, i} - 3 \times 2 ^ i\)，于是我们直接矩阵快速幂递推出前两项，后面的直接使用快速幂即可。
#include<bits/stdc++.h>
using namespace std;
#define N 5
#define Mod 1000000007
#define rep(i, l, r) for(int i = l; i <= r; ++i)
struct mat{
int g[N][N];
void clear(){ memset(g, 0, sizeof(g));}
}f, tr, ans;
int n, x, m;
int read(){
char c; int x = 0, f = 1;
c = getchar();
while(c > ‘9‘ || c < ‘0‘){ if(c == ‘-‘) f = -1; c = getchar();}
while(c >= ‘0‘ && c <= ‘9‘) x = x * 10 + c - ‘0‘, c = getchar();
return x * f;
}
int Inc(int a, int b){
return (a += b) >= Mod ? a - Mod : a;
}
int Dec(int a, int b){
return (a -= b) < 0 ? a + Mod : a;
}
int Mul(int a, int b){
return 1ll * a * b % Mod;
}
int Qpow(int a, int b){
int ans = 1;
while(b){
if(b & 1) ans = Mul(ans, a);
a = Mul(a, a), b >>= 1;
}
return ans;
}
mat mul(mat a, mat b){
mat c; c.clear();
rep(i, 1, 3) rep(j, 1, 3) rep(k, 1, 3) c.g[i][j] = Inc(c.g[i][j], Mul(a.g[i][k], b.g[k][j]));
return c;
}
int main(){
n = read(), m = read(); if(n > m) swap(n, m);
if(n == 1) printf("%d", Qpow(2, m));
else if(n == 2) printf("%d", Mul(12, Qpow(3, m - 2)));
else if(n == 3) printf("%d", Mul(112, Qpow(3, m - 3)));
else{
f.g[1][1] = 912, f.g[1][2] = 2688, f.g[1][3] = 32;
tr.g[1][1] = 2, tr.g[1][2] = 6, tr.g[1][3] = 0;
tr.g[2][1] = 2, tr.g[2][2] = 6, tr.g[2][3] = 0;
tr.g[3][1] = -2, tr.g[3][2] = -9, tr.g[3][3] = 2;
ans.g[1][1] = ans.g[2][2] = ans.g[3][3] = 1;
x = n - 4;
while(x){
if(x & 1) ans = mul(ans, tr);
tr = mul(tr, tr), x >>= 1;
}
f = mul(f, ans);
if(n == m) printf("%d", f.g[1][1]);
else printf("%d", Mul(f.g[1][2], Qpow(3, m - n - 1)));
}
return 0;
}
原文：https://www.cnblogs.com/Go7338395/p/13334959.html