A Monotonic Matrix(详解）
A Monotonic Matrix
感谢楼下指正@Ruger
先备知识
LGV 算法 (Lindström–Gessel–Viennot lemma)
求以上矩阵的行列式，其中 e(a,b) 是从a到b的方法数，带入求行列式即可得到(a1,a2,...an) 到 (b1,b2,...bn) 的所有不相交路径的种数
思路
考虑01和12的分界线
是(n, 0)到(0，m)的两条不相交（可重合）路径
分界线以及分界线以上的点是一种，分界线下是一种
平移其中一条变成(n-1, -1)到(-1，m-1);
变成
然后进行预处理打表前2*n的阶乘和阶乘逆元就行了
#include <bits/stdc++.h>
#define mem(ar,num) memset(ar,num,sizeof(ar))
#define me(ar) memset(ar,0,sizeof(ar))
#define lowbit(x) (x&(-x))
#define Pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int prime = 999983;
const int INF = 0x7FFFFFFF;
const LL INFF =0x7FFFFFFFFFFFFFFF;
const double PI = acos(-1.0);
const double inf = 1e18;
const double eps = 1e-6;
const LL mod = 1e9 + 7;
int dr[2][4] = {1,-1,0,0,0,0,-1,1};
typedef pair<int,int> P;
LL qpow(LL a,LL b){
LL ans = 1;
a %= mod;
while( b > 0){
if(b&1) ans = ans*a%mod;
a = a*a%mod;
b >>= 1;
}
return ans;
}
const int maxn = 2e3+100;
LL fac[maxn],invfac[maxn];
void init(void){
fac[0] = 1;
invfac[0] = 1;
for(int i = 1;i < maxn; ++i)
fac[i] = fac[i-1]*i%mod,invfac[i] = qpow(fac[i],mod-2);
}
int main(void)
{
init();
LL n,m;
while(scanf("%lld %lld",&n,&m) != EOF){
LL ans = (fac[m+n]*invfac[m]%mod*invfac[n]%mod);
ans = ans*ans%mod;
ans = ans - fac[m+n]*fac[m+n]%mod*invfac[n+1]%mod*invfac[n-1]%mod * invfac[m+1]%mod * invfac[m-1]%mod;
ans = (ans%mod + mod)%mod;
printf("%lld\n",ans);
}
return 0;
} 
商汤科技二面4人在聊
查看10道真题和解析