牛客网暑期ACM多校训练营(第一场) A Monotonic Matrix

  • 2018-07-26
  • 13
  • 0

题目:

Count the number of n x m matrices A satisfying the following condition modulo (109+7).
* Ai, j ∈ {0, 1, 2} for all 1 ≤ i ≤ n, 1 ≤ j ≤ m.
* Ai, j ≤ Ai + 1, j for all 1 ≤ i < n, 1 ≤ j ≤ m.
* Ai, j ≤ Ai, j + 1 for all 1 ≤ i ≤ n, 1 ≤ j < m.

Input:

The input consists of several test cases and is terminated by end-of-file.
Each test case contains two integers n and m.

Output:

For each test case, print an integer which denotes the result.

Sample Input:

1 2
2 2
1000 1000

Sample Output:

6
20
540949876

题目链接

题目要求找出有多少种满足条件的矩阵填充方案数,我们可以用两条线把整个矩阵划分为0、1、2三部分,如图:

这时问题就变为了求起点(m,0)到终点(0,n)的两条可重合但不相交的路径数。

Lindström–Gessel–Viennot lemma – Wikipedia

LGV算法可以通过公式

求出网格图不相交路径数量(设所有路径起点集合为A = {a_1,a_2…a_n},终点集合为B = {b_1,b_2…b_n}e(a_1,b_1)是从起点a_1到终点b_1路径的方案数(若a_1=(m,0),b_1=(0,n)e(a_1,b_1)=C_{n+m}^{n}))。

这道题目要求的是两条可重合但不相交的路径数,比LGV算法多了可重合的情况,那么考虑平移其中一条路径到起点(m-1,-1)终点(-1,n-1)(这样通过计算之后再把这条路径平移回去两条路径就可以有重合的情况),此时A = {a_1:(m,0),a_2:(m-1,-1)},B = {b_1:(0,n),b_2:(-1,n-1)},可以直接通过LGV算法求出这两条路径方案数。

AC代码:

评论

还没有任何评论,你来说两句吧