什么是矩阵追踪？

Question

下面给出的是英语词典中排列为矩阵的单词

MATHE
ATHEM
THEMA
HEMAT
EMATI
MATIC
ATICS

跟踪矩阵从左上角开始,每步向右或向下移动,到达矩阵的右下角.确保任何此类跟踪都生成相同的单词.对于长度为m + n-1的给定单词写成大小为m*n的矩阵,可以有多少这样的跟踪？

输入格式第一行输入包含一个整数T.每行都有T个测试用例.每行包含2个空格分隔的整数m和n,表示写入的矩阵有m行,每行有n个字符.

约束:

1 <= T <= 103
1 ? m,n ? 106

输出格式打印可以跟踪单词的方式(S)的数量,如问题陈述中所述.如果数字大于10,则为9 +7,请打印S mod(10 rest to power 9 +7)

样本输入

1
2 3

样本输出

3

解释让我们考虑写为矩阵的单词AWAY

AWA
WAY

在这里,矩阵中的单词AWAY可以用3种不同的方式跟踪,遍历RIGHT或DOWN.

AWA
  Y

AW
 AY

A
WAY

Answer 1

这是一个很好的问题,这就是我将回答它的原因.然而,它似乎是一个家庭作业,或者是从奥林匹克运动会中获得的一个问题,这就是为什么你有这么多的downvotes.答案是我们有(N-1 + M-1)!/((N- 1)!(M-1)!)给定M和N的不同路径.例如对于样本输入,我们有(2-1 + 3-1)!/((2-1)!(3-1) !)= 3!/(1*2),即6/2 = 3.

这是因为将有M-1移动RIGHT和N-1移动DOWN.

因此,对于您的例子我们可以

右下方

正确的权利

向下右

所以这些只是M-1 RIGHT和N-1 DOWN的排列.就如此容易.

这是简化的(从文件读取等,被删除)算法

long getResult(int N, int M){
return Math.Factorial(N +M -2)/(Math.Factorial(N-1)*Math.Factorial(M-1));
}

希望能帮助到你