Description:
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={a1,a2...an},终点集合为 B={b1,b2...bn}, e(a1,b1)是从起点 a1到终点 b1路径的方案数(若 a1=(m,0),b1=(0,n)则 e(a1,b1)=Cn+mn))。
这道题目要求的是两条可重合但不相交的路径数,比LGV算法多了可重合的情况,那么考虑平移其中一条路径到起点 (m−1,−1)终点 (−1,n−1)(这样通过计算之后再把这条路径平移回去两条路径就可以有重合的情况),此时 A={a1:(m,0),a2:(m−1,−1)},B={b1:(0,n),b2:(−1,n−1)},可以直接通过LGV算法求出这两条路径方案数。
AC代码:
#pragma comment(linker, "/STACK:102400000,102400000")
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF = 0x3f3f3f3f;
const int maxn = 2e3 + 5;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = asin(1.0) * 2;
const double e = 2.718281828459;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
int n, m;
ll C[maxn][maxn];
// 打表计算组合数
void CombinatorialNumber() {
C[0][0] = 1;
for (int i = 1; i < maxn; ++i) {
C[i][0] = 1;
for (int j = 1; j <= i; ++j) {
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
}
}
}
int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
CombinatorialNumber();
while (~scanf("%d %d", &n, &m)) {
ll ans = C[m + n][n] * C[m + n][n] % mod - (C[n + m][m - 1] % mod) * (C[n + m][m + 1] % mod) % mod;
while (ans < 0) {
ans += mod;
}
printf("%lld\n", ans);
}
#ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stdout);
system("gedit out.txt");
#endif
return 0;
}