竞赛讨论区 > A Monotonic Matrix(详解)
头像
秋招没工作
编辑于 2018-08-29 20:26
+ 关注

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;
} 

全部评论

(3) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐