题意：两只乌龟从1 1走到n m，只能走没有'#'的位置，问你两只乌龟走的时候不见面的路径走法有几种
思路：LGV定理模板。但是定理中只能从n个不同起点走向n个不同终点，那么需要转化。显然必有一只从1, 2走到 n - 1, m，另一只从2, 1走到 n, m - 1。
代码：
#include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxn = 3000 + 10; const int M = maxn * 30; const ull seed = 131; const int INF = 0x3f3f3f3f; const int MOD = 1000000007; char mp[maxn][maxn]; ll dp[maxn][maxn]; ll e[5][5]; ll guass(int n, ll p){ ll ans = 1, f = 1; for(int i = 1; i <= n; i++){ for(int j = i + 1; j <= n; j++){ int x = i, y = j; while(e[y][i]){ ll t = e[x][i] / e[y][i]; for(int k = i; k <= n; k++) e[x][k] = (e[x][k] - e[y][k] * t % p) % p; swap(x,y); } if(x != i){ for(int k = 1; k <= n; k++) swap(e[i][k], e[j][k]); f = -f; } } ans = ans * e[i][i] % p; if(ans == 0) return 0; } return (ans * f + p) % p; } int main(){ int n, m; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) scanf("%s", mp[i] + 1); memset(dp, 0, sizeof(dp)); dp[1][2] = 1; for(int i = 1; i <= n; i++){ for(int j = 2; j <= m; j++){ if(i == 1 && j == 2) continue; if(mp[i][j] == '#') continue; dp[i][j] = 0; if(j - 1 >= 1 && mp[i][j - 1] != '#') dp[i][j] += dp[i][j - 1]; if(i - 1 >= 1 && mp[i - 1][j] != '#') dp[i][j] += dp[i - 1][j]; dp[i][j] = dp[i][j] % MOD; } } e[1][1] = dp[n - 1][m], e[1][2] = dp[n][m - 1]; memset(dp, 0, sizeof(dp)); dp[2][1] = 1; for(int i = 2; i <= n; i++){ for(int j = 1; j <= m; j++){ if(i == 2 && j == 1) continue; if(mp[i][j] == '#') continue; dp[i][j] = 0; if(j - 1 >= 1 && mp[i][j - 1] != '#') dp[i][j] += dp[i][j - 1]; if(i - 1 >= 1 && mp[i - 1][j] != '#') dp[i][j] += dp[i - 1][j]; dp[i][j] = dp[i][j] % MOD; } } e[2][1] = dp[n - 1][m], e[2][2] = dp[n][m - 1]; printf("%lld\n", guass(2, MOD)); return 0; }
手机扫一扫
移动阅读更方便
你可能感兴趣的文章
