# 牛客多校第一場A——Monotonic Matrix（數論——組合數學—— Lindström–Gessel–Viennot lemma ）

1. 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.

1 2

2 2

1000 1000

6

20

540949876

Lindström–Gessel–Viennot Lemma

AC程式碼：

# Lindström–Gessel–Viennot Lemma

M:=(e(a1,b1)e(a1,b2)⋯e(a1,bm) e(a2,b1)e(a2,b2)⋯e(a2,bm) ⋮⋮⋱⋮ e(an,b1)e(an,b2)⋯e(an,bm))M:=(e(a1,b1)e(a1,b2)⋯e(a1,bm) e(a2,b1)e(a2,b2)⋯e(a2,bm) ⋮⋮⋱⋮ e(an,b1)e(an,b2)⋯e(an,bm))

# AC程式碼：

``````#include<bits/stdc  .h>
#include<ctime>
using namespace std;
const int N = 2e3   7;
const int mod = 1e9   7;
long long jie[N],ni[N];
void get_jie()
{
jie[0] = 1;
for(int i = 1; i < N;  i)   jie[i] = (jie[i - 1] * i) % mod;
}
long long fpow_mod(long long a,long long b)
{
long long res = 1;
while(b){
if(b & 1) res = (res * a) % mod;;
a = (a * a) % mod;
b >>= 1;
}
return res;
}
void get_inv()
{
for(int i = 0;i < N;  i)
ni[i] = fpow_mod(jie[i],mod - 2);
}
inline long long con(int n,int m)
{
return (jie[n] * ni[m]) % mod * ni[n - m] % mod;
}
int main()
{
int n,m;
get_jie();
get_inv();
while(cin >> n >> m){
long long ans = 0;
ans = con(n   m,n);
ans = (ans * ans) % mod;
ans = ans - (con(n   m,m - 1) * con(n   m,n - 1)) % mod;
/*if(n == 1 || m == 1){
if(n < m) swap(n,m);
ans = 2   n   (n   2) * (n - 1) / 2;
}*/
ans = (ans   mod) % mod;
cout << ans << endl;
}
return 0;
}
``````