\(\mathcal{Description}\)

link.

给定一个 \(n\times m\) 的网格图，一些格子指定了走出该格的方向（上下左右），而有 \(k\) 格可以任意指定走出方向。求指定的方案数，使得从任意格子都可以走出网格图。

\(n,m\le200;k\le300\)。

\(\mathcal{Solution}\)

令“走出边界”为走到一个特殊点，建图，其中未指定方向的点向四周连边，相当于求以特殊点为根的内向树个数，跑矩阵树定理即可。复杂度 \(\mathcal O(n^3m^3)\)。

考虑优化，生成树个数实质上只与不定向的点有关，所以直接预处理出每个不定向点向上/下/左/右走到的第一个不定向点，向其连边，再跑矩阵树。复杂度 \(\mathcal O(k^3)\)。

\(\mathcal{Code}\)

#include <cstdio>

#include <cstring>

#include <iostream>

const int MOD = 1e9 + 7, MAXN = 200, MAXP = 300;

int T, N, M, K[MAXP + 5][MAXP + 5], col[MAXN + 5][MAXN + 5], unk[MAXN + 5][MAXN + 5], cnt;

char gar[MAXN + 5][MAXN + 5];

inline int qkpow ( int a, int b, const int p = MOD ) {

	int ret = 1;

	for ( ; b; a = 1ll * a * a % p, b >>= 1 ) ret = 1ll * ret * ( b & 1 ? a : 1 ) % p;

	return ret;

}

inline int det ( const int n ) {

	int ret = 1, swp = 1;

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

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

			if ( K[j][i] ) {

				if ( i ^ j ) std::swap ( K[i], K[j] ), swp *= -1;

				break;

			}

		}

		if ( ! ( ret = 1ll * ret * K[i][i] % MOD ) ) return 0;

		for ( int j = i + 1, inv = qkpow ( K[i][i], MOD - 2 ); j <= n; ++ j ) {

			int d = 1ll * K[j][i] * inv % MOD;

			for ( int k = i; k <= n; ++ k ) K[j][k] = ( K[j][k] - 1ll * K[i][k] * d % MOD + MOD ) % MOD;

		}

	}

	return ( ret * swp + MOD ) % MOD;

}

inline bool findLoop ( const int x, const int y, const int cur ) {

	if ( x < 1 || x > N || y < 1 || y > M || gar[x][y] == '.' ) return false;

	if ( col[x][y] == cur ) return true;

	if ( col[x][y] ) return false;

	col[x][y] = cur;

	if ( gar[x][y] == 'L' ) return findLoop ( x, y - 1, cur );

	if ( gar[x][y] == 'R' ) return findLoop ( x, y + 1, cur );

	if ( gar[x][y] == 'U' ) return findLoop ( x - 1, y, cur );

	if ( gar[x][y] == 'D' ) return findLoop ( x + 1, y, cur );

	return false;

}

inline int findUnknown ( const int x, const int y ) {

	if ( x < 1 || x > N || y < 1 || y > M ) return 1;

	if ( unk[x][y] ) return unk[x][y];

	int& ret = unk[x][y];

	if ( gar[x][y] == 'L' ) ret = findUnknown ( x, y - 1 );

	if ( gar[x][y] == 'R' ) ret = findUnknown ( x, y + 1 );

	if ( gar[x][y] == 'U' ) ret = findUnknown ( x - 1, y );

	if ( gar[x][y] == 'D' ) ret = findUnknown ( x + 1, y );

	return ret;

}

inline void add ( const int s, int t ) {

	if ( ! t ) t = 1;

	++ K[s][s], -- K[s][t];

	if ( K[s][t] < 0 ) K[s][t] += MOD;

}

int main () {

	for ( scanf ( "%d", &T ); T --; ) {

		memset ( K, 0, sizeof K );

		memset ( col, 0, sizeof col );

		memset ( unk, 0, sizeof unk );

		scanf ( "%d %d", &N, &M ), cnt = 1;

		for ( int i = 1; i <= N; ++ i ) {

			scanf ( "%s", gar[i] + 1 );

			for ( int j = 1; j <= M; ++ j ) {

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

					unk[i][j] = ++ cnt;

				}

			}

		}

		bool loop = false;

		for ( int i = 1, cur = 1; i <= N && ! loop; ++ i ) {

			for ( int j = 1; j <= M && ! loop; ++ j ) {

				loop |= findLoop ( i, j, cur ++ );

			}

		}

		if ( loop ) { puts ( "0" ); continue; }

		for ( int i = 1; i <= N; ++ i ) {

			for ( int j = 1; j <= M; ++ j ) {

				findUnknown ( i, j );

			}

		}

		for ( int i = 1; i <= N; ++ i ) {

			for ( int j = 1; j <= M; ++ j ) {

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

					add ( unk[i][j], unk[i][j - 1] );

					add ( unk[i][j], unk[i][j + 1] );

					add ( unk[i][j], unk[i - 1][j] );

					add ( unk[i][j], unk[i + 1][j] );

				}

			}

		}

		printf ( "%d\n", det ( cnt ) );

	}

	return 0;

}

巴特西

Solution -「Code+#2」「洛谷 P4033」白金元首与独舞

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

最新文章

热门文章