D. Turtles

题意：

　　给定一个N*M的棋盘，有些格子不能走，问有多少种从(1,1)到(N,M)的两条不相交路径。

分析：

　　定理：点集A={a1,a2,…an}A={a1,a2,…an}到B={b1,b2,…bn}B={b1,b2,…bn}的不相交路径条数等于下面矩阵的行列式。

　　$$\begin{bmatrix} e(a_1, b_1) & e(a_1, b_2) & \dots & e(a_1, b_n) \\ e(a_2, b_1) & e(a_2, b_2) & \dots & e(a_2, b_n) \\ \dots & \dots & \dots & \dots \\ e(a_n, b_1) & e(a_n, b_2) & \dots & e(a_n, b_n) \\ \end{bmatrix}$$

　　e(a,b)为从点a到点b的路径条数，本质是容斥。

　　这道题目中，任意一条合法的路径都是从(1,2)->(n-1,m)和(2,1)->(n,m-1)的，所以$A=\{(1,2),(2,1)\}$，$B=\{(n-1,m),(n,m-1)\}$。　　

代码：

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cmath>

#include<cctype>

#include<set>

#include<queue>

#include<vector>

#include<map>

using namespace std;

typedef long long LL;

inline int read() {

    int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

    for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

}

const int N = , mod = 1e9 + ;

int f[N][N];

char s[N][N];

int Calc(int a,int b,int c,int d) {

    memset(f, , sizeof(f));

    for (int i = a; i <= c; ++i)

        for (int j = b; j <= d; ++j)

            if (s[i][j] == '.') {

                if (i == a && j == b) f[i][j] = ;

                else f[i][j] = (f[i - ][j]  + f[i][j - ]) % mod;

            }

    return f[c][d];

}

int main() {

    int n = read(), m = read();

    for (int i = ; i <= n; ++i) scanf("%s", s[i] + );

    LL t1 = Calc(, , n - , m), t2 = Calc(, , n, m - );

    LL t3 = Calc(, , n, m - ), t4 = Calc(, , n - , m);

    cout << (t1 * t2 % mod - t3 * t4 % mod + mod) % mod;

    return ;

}

dots

CF 348 D. Turtles

D. Turtles