Codeforces 348D Turtles LGV

Turtles

利用LGV转换成求行列式值。

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define PLL pair<LL, LL>

#define PLI pair<LL, int>

#define PII pair<int, int>

#define SZ(x) ((int)x.size())

#define ull unsigned long long

using namespace std;

const int N =  + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + ;

const double eps = 1e-;

const double PI = acos(-);

int n, m, dp1[N][N], dp2[N][N];

char s[N][N];

void solve(int sx, int sy, int dp[N][N]) {

    if(s[sx][sy] != '#') dp[sx][sy] = ;

    for(int i = ; i <= n; i++) {

        for(int j = ; j <= m; j++) {

            if(s[i][j] == '#') continue;

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

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

        }

    }

}

int main() {

    scanf("%d%d", &n, &m);

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

    solve(, , dp1);

    solve(, , dp2);

    printf("%d\n", (1ll * dp1[n - ][m] * dp2[n][m - ] % mod  - 1ll * dp1[n][m - ] * dp2[n - ][m] % mod + mod) % mod);

    return ;

}

/*

*/