Lindström–Gessel–Viennot引理

对于一张无边权的DAG图，给定n个起点和对应的n个终点，这n条不相交路径的方案数为

其中e(a,b)为图上a（起点）到b（终点）的方案数。

---

CodeForces348D

题意：

给出一张n*m的有障碍的图，问从(1,1)到(n,m)不相交的两条路径的方案。其中$2<=n,m<=3000$。

思路：

可以将起点看作$A_1(1,2)$和$A_2(2,1)$，将终点看作$B_1(n-1,m)$和$B_2(n,m-1)$（不能换，因为这样$A_1B_1$和$A_2B_2$路径是不相交的，如果换了以后这两条路径肯定是会相交的），路径肯定是$(1,2)->(n-1,m)$和$(2,1)->(n,m-1)$这两条，否则是会相交的。

设$S(x,y)$为从x到y的方案数。

根据LGV引理，答案为$S(A1,B1)*S(A2,B2)-S(A1,B2)*S(A2,B1)$。

因为是有障碍的而且范围可以进行DP，所以DP求出$S(x,y)$就可以了。

如果没有障碍的话可以直接组合数，比如从(1,1)到(n,m)为$C_{n+m-2}^{n-1}$（总共要走n+m-2步其中有n-1步是往下走的）。

代码：

char mp[3010][3010];
ll dp[3010][3010];
int main()
{
    int r,c;
    ll ans11,ans12,ans21,ans22;
    scanf("%d%d",&r,&c);
    for(int i=1;i<=r;i++)
        scanf("%s",mp[i]+1);
    memset(dp,0,sizeof(dp));
    if(mp[1][2]=='.')dp[1][2]=1;
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)
        {
            if(mp[i][j]=='#')continue;
            if(i-1>=1&&mp[i-1][j]=='.')
                dp[i][j]=(dp[i][j]+dp[i-1][j])%MOD;
            if(j-1>=1&&mp[i][j-1]=='.')
                dp[i][j]=(dp[i][j]+dp[i][j-1])%MOD;
        }
    ans11=dp[r-1][c];ans12=dp[r][c-1];
    if(mp[2][1]=='.')dp[2][1]=1;
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)
        {
            if(mp[i][j]=='#')continue;
            if(i-1>=1&&mp[i-1][j]=='.')
                dp[i][j]=(dp[i][j]+dp[i-1][j])%MOD;
            if(j-1>=1&&mp[i][j-1]=='.')
                dp[i][j]=(dp[i][j]+dp[i][j-1])%MOD;
        }
    ans21=dp[r-1][c];ans22=dp[r][c-1];
    printf("%lld\n",((ans11*ans22)%MOD-(ans12*ans21)%MOD+MOD)%MOD);
    return 0;
}

---

牛客网暑期ACM多校训练营（第一场）A

题意：

要求满足以下条件的n*m的矩阵个数模1e9+7：

$$A_{i,j}∈ {0, 1, 2}$$ $$A_{i,j}\leq A_{i+1,j}$$

$A_{i, j}\leq A_{i,j+1}$。

思路：

考虑01和12的分界线，是$(n,0)$到$(0,m)$的两条不相交（可重合）路径。因为两个起点重合了，所以平移其中一条变成$(n-1,-1)$到$(-1,m-1)$。

所以将起点看作$(n,0)$和$(n-1,-1)$，把终点看作$(0,m)$和$(-1,m-1)$。

之后就可以用LGV公式了。

所以答案是${C_{n+m}^{n}}^{2}-C_{n+m}^{m-1}*C_{n+m}^{n-1}$。

所以分界线将矩阵分为三部分。

我之前有个疑问，为什么不仍然像上面那道题一样分成两个那样的起点和终点呢？

结合上面那张图考虑了一下，这样子分是会有遗漏的，就只有这张图的这些情况了，就少了一些，就是说分界线中间相差的不止是一格，而以上那样的相差的就是一格。

代码：

ll c[2010][2010];
void init()
{
    c[0][0]=1;
    for(ll i=1;i<=2000;i++)//j是上面，i是下面
    {
        c[i][0]=1;
        for(ll j=1;j<=i;j++)
        {
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%MOD;
            //printf("%lld %lld %lld\n",i,j,c[i][j]);
        }
    }
}
int main()
{
    init();
    long long n,m;
    while(scanf("%lld%lld",&n,&m)!=EOF)
    {
        ll temp1=c[n+m][n];
        ll temp2=c[n+m][m-1];
        ll temp3=c[n+m][n-1];
        //printf("%lld %lld %lld\n",temp1,temp2,temp3);
        printf("%lld\n",((temp1*temp1)%MOD-(temp2*temp3)%MOD+MOD)%MOD);
    }
    return 0;
}