LGV算法 CodeForces 348D + 牛客多校 A Monotonic Matrix

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了LGV算法 CodeForces 348D + 牛客多校 A Monotonic Matrix，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1377字，纯文字阅读大概需要2分钟。

内容图文

定理（Lindström–Gessel–Viennot lemma）很简单：

学的时候忘了大的行列式怎么算的了。。

 

 

 然后就可以写题了：

第一道：CodeForces-348D（链接https://vjudge.net/problem/CodeForces-348D）

题意给你个n*m的方阵，有一些点无法通过，然后求从(1,1)到(n,m)走两条路，并且两条路不相交的方案数。

题解：只能向右或者向下走，那么起始点肯定一个向左一个向右，结束点肯定一个从上方过来，一个从左方过来，那么题就成了两个点（1，2）（2，1）到两个点（n-1，m）（n，m-1）。就能写了。

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define met(a, b) memset(a, b, sizeof(a))
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define bep(i, a, b) for(int i = a; i >= b; i--)
#define re return 0
using namespace std;
const ll mod = 1e9 + 7;
const double PI = acos(-1);
const ll INF = 2e18+1;
const int inf = 1e9 + 15;
const double eps = 1e-7;
const int maxn = 1e6 + 5;
ll d[3003][3003], p[3003][3003];
string ma[3003];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, m; cin >> n >> m;
    n--, m--;
    rep(i, 0, n) cin >> ma[i];
    d[0][0] = p[0][0] = 1;
    rep(i, 0, n){
        rep(j, 1, m){
            if(ma[i][j] == '.'){
                if(i) d[i][j] += d[i-1][j];
                if(j) d[i][j] += d[i][j-1];
                d[i][j] %= mod;
            }
        }
    }
    rep(i, 1, n){
        rep(j, 0, m){
            if(ma[i][j] == '.'){
                if(i) p[i][j] += p[i-1][j];
                if(j) p[i][j] += p[i][j-1];
                p[i][j] %= mod;
            }
        }
    }
    cout << ((d[n-1][m]*p[n][m-1])%mod - (d[n][m-1]*p[n-1][m])%mod + mod) % mod << endl;
    re;
}

 

内容总结

以上是互联网集市为您收集整理的LGV算法 CodeForces 348D + 牛客多校 A Monotonic Matrix全部内容，希望文章能够帮你解决LGV算法 CodeForces 348D + 牛客多校 A Monotonic Matrix所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---