CF348D Turtles

经典题。

容易发现两条不相交的路径一定是 $(1,2)\to (n-1,m)$ 和 $(2,1)\to (n,m-1)$。但是这只具有充分性，似乎并没有什么帮助。

这个时候巧妙的来了，我们发现 $(1,2)\to (n,m-1)$ 与 $(2,1)\to (n-1,m)$ 是一定有交的。并且每一种方案恰好对应着原来 $(1,2)\to (n-1,m)$ 和 $(2,1)\to (n,m-1)$ 有交的一种方案（在每个交点改变两条路径连向就可以得到原来有交的一种方案）。于是直接减去这一部分就得到了没有交的路径方案数。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=3e3+10,mod=1e9+7;
template<class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n,m;
int a[N][N];
int f[N][N];
inline int adj(int x){return (x>=mod)?x-mod:x;}
inline int calc(int x1,int y1,int x2,int y2)
{
    memset(f,0,sizeof(f));
    f[x1][y1]=a[x1][y1];
    for(int i=x1;i<=x2;i++)
        for(int j=y1;j<=y2;j++)
        {
            if((i==x1&&j==y1)||!a[i][j])continue;
            f[i][j]=adj(f[i-1][j]+f[i][j-1]);
        }
    return f[x2][y2];
}
int main()
{
    read(n,m);
    for(int i=1;i<=n;i++)
    {
        char ch[N];
        scanf("%s",ch+1);
        for(int j=1;j<=m;j++)a[i][j]=(ch[j]=='.');
    }
    printf("%d\n",adj(1ll*calc(1,2,n-1,m)*calc(2,1,n,m-1)%mod-1ll*calc(1,2,n,m-1)*calc(2,1,n-1,m)%mod+mod));
    return 0;
}