题目描述

小D特别喜欢玩游戏。这一天，他在玩一款填数游戏。
这个填数游戏的棋盘是一个的矩形表格。玩家需要在表格的每个格子中填入一个数字（数字0或者数字1），填数时需要满足一些限制。
下面我们来具体描述这些限制。
为了方便描述，我们先给出一些定义：
• 我们用每个格子的行列坐标来表示一个格子，即（行坐标，列坐标）。（注意：行列坐标均从0开始编号）
• 合法路径P：一条路径是合法的当且仅当：
1. 这条路径从矩形表格的左上角的格子出发，到矩形的右下角格子 结束；
2. 在这条路径中，每次只能从当前的格子移动到右边与它相邻的格子，或者从当前格子移动到下面与它相邻的格子。
例如：在下面这个矩形中，只有两条路径是合法的，它们分别是Pi: (0, 0) → (0, 1) → (1, 1)和P2:(0, 0) → (1, 0) → (1, 1)

对于一条合法的路径P，我们可以用一个字符串w(P)来表示，该字符串的长度为n + m - 2，其中只包含字符“R”或者字符“D”，第i个字符记录了路径P中第i步的移动方法，“R”表示移动到当前格子右边与它相邻的格子，“D”表示移动到当前格子下面与它相邻的格子。例如，上图中对于路径P1，有w(P1) = "RD"；而对于另一条路径P2，有w(P2) = "DR"。
同时，将每条合法路径P经过的每个格子上填入的数字依次连接后，会得到一个长度为n + m - 1的01字符串，记为s(P)。例如，如果我们在格子(0, 0)和(1, 0)上填入数字0，在格子(0, 0)和(1, 1)上填入数字1（见上图红色数字）。那么对于路径P1，我们可以得到s(P1) = "011",对于路径P2，有s(P2) = "001"。
游戏要求小D找到一种填数字0、1的方法，使得对于两条路径P1，P2，如果w(P1) > w(P2) ，那么必须s(P1) <= s(P2)。我们说字符串a比字符串b小，当且仅当字符串a的字典序小于字符串b的字典序，字典序的定义详见第一题。但是仅仅是找一种方法无法满足小D的好奇心，小D更想知道这个游戏有多少种玩法，也就是说，有多少种填数字的方法满足游戏的要求？
小D能力有限，希望你帮助他解决这个问题，即有多少种填0、1的方法能满足题目要求。由于答案可能很大，你需要输出答案对109 + 7取模的结果。


输入描述:

输入共一行，包含两个正整数n、m，由一个空格分隔，表示矩形的大小。其中n 表示矩形表格的行数，m表示矩形表格的列数。

输出描述:

输出共一行，包含一个正整数，表示有多少种填0、1的方法能满足游戏的要求。注意：输出答案对取模的结果。

示例1

输入
2 2
输出
12
说明

对于2 × 2棋盘，有上图所示的 12 种填数方法满足要求。

示例2

输入
3 3
输出
112

示例3

输入
5 5
输出
7136

备注


解答

这道题讲道理还是不错的，因为你需要不断挖掘其中的性质来帮助解题。可惜数据范围开在这里让考试时的我很慌，勉强也就写了65 分就没了。回忆在考场上，思路是没有错的，就是发掘不够深入，思路还不够清晰。事实上考场上没有选择继续做这道题是对的，因为就算是我考后仔细分析之后，写完这道题仍然花了我不少时间。

我们可以循着思路一步步分析，一步步得到每一个性质。

 题目中对其走过路径的字典序的比较提示我们按斜行分析。稍加思考我们就能得到一个明显的结论，就是对于某一个格子如果它是1 ，那它的右上角的那个格子就不能是0 ，这几乎就是题目条件的定义，因为有一条路径走到了这个格子，它就会在分叉的时候出问题。我们它这个性质总结一下就能得到我们需要的第一个结论：

1.对于每一个斜行，其0/ 1状态一定是存在一个分界点，使得其左下方都是1，其右上方都是0。

有以上的结论将大大减少每一个斜行的可行的0/1状态。我们接着思考，一对不合法的路径的出现，除了上述的情况，都可以归结为两条不同的路径以相同的0/1串走到了某一个格子，但是这个格子右边下边的两个格子的0/1是不同的，这同样会让矛盾出现。或许你会想这两条路径在0/1字典序出现分歧的时候并不一定在同一个格子里，但如果存在这种情况，那我们一定能找到前者所说的更加简单的情况。我们将形式地描述这个问题，我们称一个格子是“模糊”的，当且仅当存在两条不同的路径以相同的0/1串走到了这个格子。我们所发现的可以表述成：

2.如果某一个格子它左边上边的两个格子的0/1 是相同的，或者它左边或上边有格子是模糊点，那这个格子就是模糊点；模糊点右边下边的两个格子的0/1 必须相同。

这也是一个重要的结论，它为下一个结论的得到提供了一个有力的帮助。模糊点的传递性隐约让我们感觉到它们的排布不会错杂无序，事实上十分有规律。读者可以仔细推敲，利用归纳法简单证明以下结论：

3.去除第一行和第一列的格子后，每一条斜行最多只有一个格子是非模糊的，并且这个非模糊点一定在第二行或第二列。

这个性质令人惊讶，但它是真实的，并且不难证明。有了这个结论后，我们就可以有一个大致的想法，我们可以枚举整张图的模糊状态，状态数是的，因为斜行上一旦全是模糊点，接下来也一定都是模糊点。我们考虑对于一个给定的模糊状态，我们怎么去计算有多少0/1 的填放方式满足整张图的模糊状态。假设我们枚举那个仅存的非模糊点最后出现在哪一个斜行，手模一下可以发现，为了保证这个非模糊点没有消失，前面的大多数斜行的0/1 状态是唯一的，只有最开头的两斜行会有多种状态，并且为了让这个非模糊点在下一斜行中消失，这行和下一行的可行状态数也可以知道，那么算到这里方案数还是一个已知的常数。在非模糊点消失后，接下来每一斜行面临的决策都是一样的，对于后面的方案数只要快速幂即可。到这里为止，已经可以解决这道题了，利用此算法的复杂度是。

讲到这里算法大致结束了。对于上述算法而言，我们枚举了非模糊点最后出现的位置然后算方案数，其算式的形式是相同的，我们可以把其中的式子化简一下，就能用等比数列求和直接算了，在此处当的时候要求有33的逆元。所以，总复杂度为。这道题的细节相当复杂，其中的有许多常数要手动算出来，也有一些角落需要特判，就算大致知道怎么做了之后实现起来也是不容易的。

这份代码是的实现，写的时候也是有点逻辑顺序在里面的，总的来说是按照斜行的从上到下。可能其中有需要解释的地方，C函数用于求在斜行后全部都是模糊点的方案数的计算，one more case中是一个算非模糊点在第二列最后两个位置时特判，dd line是非模糊点在第n斜行的特判，last case是非模糊点在第二行最后两个位置时的特判。 

#include <cstdio>
#include <algorithm>

typedef long long LL;

const int MOD = (int)1e9 + 7;

int n, m, ans, p2, p3;

int Pow(int x, int b) {
  int r = 1;
  for (; b; b >>= 1, x = (LL)x * x % MOD) if (b & 1) r = (LL)r * x % MOD;
  return r;
}
int C(int x) { // end by x, calc after
  if (x >= m) return Pow(2, n + m - x - 1);
  if (x >= n) return (LL)Pow(3, m - x) * p2 % MOD;
  return (LL)Pow(4, n - x) * p3 % MOD * p2 % MOD;
}

int main() {
  scanf("%d%d", &n, &m);
  if (n > m) std::swap(n, m);
  p2 = Pow(2, n - 1);
  p3 = Pow(3, m - n);
  if (n == 1) {
    printf("%d\n", Pow(2, m));
    return 0;
  }
  if (n == 2) {
    printf("%lld\n", 4LL * Pow(3, m - 1) % MOD);
    return 0;
  }
  ans = (ans + 16LL * C(3)) % MOD; // on line 2
  ans = (ans + (3 + (n != 3) + (m > 3)) * 4LL * C(4)) % MOD; // on line 3
  for (int i = 4; i < n; ++i) {
    ans = (ans + 80LL * C(i + 1)) % MOD;
  }
  // one more case
  if (n > 3) {
    if (n < m) ans = (ans + 32LL * C(n + 1)) % MOD;
    else ans = (ans + 24LL * C(n + 1)) % MOD;
  }
  if (n < m) ans = (ans + 8LL * C(n + 1)) % MOD;
  else ans = (ans + 6LL * C(n + 1)) % MOD;

  // dd line
  if (n < m && n != 3) ans = (ans + 32LL * C(n + 1)) % MOD;
  for (int i = n + 1; i < m; ++i) {
    ans = (ans + 24LL * C(i + 1)) % MOD;
  }
  // last case
  if (n > 3 || m > 3) {
    if (n < m) ans = (ans + 18LL * C(m + 1)) % MOD;
    else ans = (ans + 24LL * C(m + 1)) % MOD;
  }
  ans = (ans + 6LL * C(m + 1)) % MOD;
  
  printf("%d\n", ans);
  return 0;
}
这份代码是的实现，其中把一些项合并过了，故而稍变简洁，但是无法从中得到具体的含义的。 
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long LL;

const int MOD = (int)1e9 + 7;

int n, m, ans, p2, p3;

int Pow(int x, int y) {
  int r = 1, b = (y + MOD - 1) % (MOD - 1);
  for (; b; b >>= 1, x = (LL)x * x % MOD) if (b & 1) r = (LL)r * x % MOD;
  return r;
}

int main() {
  scanf("%d%d", &n, &m);
  if (n > m) swap(n, m);
  p2 = Pow(2, n - 1);
  p3 = Pow(3, m - n);
  if (n == 1) ans = Pow(2, m);
  if (n == 2) ans = 4LL * Pow(3, m - 1) % MOD;
  if (n == 3) ans = 112LL * p3 % MOD;
  if (n > 3) {
    ans = (3LL * p2 + 21LL * Pow(2, 3 * n - 7) % MOD * p3) % MOD;
    if (n == m) ans = (ans + 27LL * p2) % MOD;
    else ans = (ans + (24LL * p3 % MOD + 9) * p2) % MOD;
    ans = (ans + 80LL * p2 % MOD * Pow(3, m - n - 1) % MOD * (Pow(4, n - 4) - 1)) % MOD;
    ans = (ans + 12LL * p2 % MOD * (Pow(3, max(0, m - n - 1)) - 1)) % MOD;
  }
  printf("%d\n", ans);
  return 0;
}

⨀⨀总结：

对于这道题的我的做法，或许与大多数做法不一定相同，它并没有要求什么算法，甚至没有类可归，重要的是要细心耐心地思考与推导。



来源：Dance Of Faith