HHKB プログラミングコンテスト 2020, E : Lamps

問題文

　https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_e

問題概要

　高さ $H$, 幅 $W$ のグリッド状の盤面がある．グリッドの各セルは '.' または '#' である．
　この盤面の，$0$ 個以上の '.' であるセルに照明を配置することを考える．照明は，配置したセル自身及び，上下左右 4 方向それぞれについてまっすぐ移動していったときに '#' にぶつかる直前のセルまでを照らす．
　'.' のセルの個数を $K$ としたとき，照明の置き方の総数は $2^K$ 個ある．そのそれぞれについての照明に照らされるセルの個数の和を（MOD で）求めよ．

制約

• $1 \leq H, W \leq 2{,}000$

解法

　$2^K$ 個ある配置のそれぞれについて考えていくと個数が多すぎて大変なので，逆（？）に，各セルについてそのセルが照らされる回数を求めることを考えます．
　あるセルを照らせるセルの個数は，$O( H + W )$ 個あるので，各セルについて毎回計算していると TLE します．なので，すべてのセルについて，そのセルを照らせるセルの個数を前計算しておきたい気持ちになります．セル $( i, j )$ について，そのセル自身を含め，上下左右のそれぞれから $( i, j )$ を照らせるセルの個数をそれぞれ $u( i, j ), d( i, j ), l( i, j ), r( i, j )$ とします．このとき，セル $( i, j )$ を照らせるセルの個数は，$u( i, j ) + d( i, j ) + l( i, j ) + r( i, j ) - 3$ 個です（$l, r, u, d$ の全てで $( i, j )$ 自身を数えているので $3$ を引く）．あとは，$u, d, l, r$ の値をある程度高速に前計算しておければ問題を解くことができます．これは，上下左右の各方向について，'.' のセルについてだけ累積和をとるような処理をすると求まります．（例えば $l$ については，セル $( i, j )$ とセル $( i, j + 1 )$ がともに存在して '.' のとき，$l( i, j + 1 ) = l( i, j ) + 1$ です．）
　あるセルについて，そこを照らせるセルの個数が $k$ 個だったとすると，その $k$ 個がとれる状態の内，実際に着目セルを照らすのは $2^k - 1$ 通りです．また，それ以外のセルについては任意の状態をとっていてよいので，$2^{ K - k }$ 通りの状態があります．なのでまとめると，着目セルが照らされるような状態の総数は $( 2^k - 1 )( 2^{ K - k } )$ 通りと求まります．これを MOD で計算しつつ和をとればよいです．
　計算量についてですが，まず累積和を 4 回やるときに $\Theta( HW )$ 時間がかかります．次に各セルについて答えを求めるとき，$2$ の冪乗の計算に反復二乗法を用いたとすれば $O( \log HW )$ 時間ずつ余計にかかり，$O( HW \log HW )$ 時間となります．入出力にかかる時間は定数倍の中に消えるので，全体では $O( HW \log HW )$ 時間となります．

コード

constexpr int MOD = 1'000'000'007;

// a^x を mod で求める
// 反復二乗法
// O( log x )
long long mod_pow( long long a, long long x, long long mod );

int main()
{
	IN( int, H, W );
	VS board( H );
	cin >> board;

	int total = 0;
	VVI from_left( H, VI( W ) ), from_right( from_left ), from_up( from_left ), from_down( from_left );
	REP( i, H )
	{
		REP( j, W )
		{
			from_left[i][j] = from_right[i][j] = from_up[i][j] = from_down[i][j] = board[i][j] == '.';
			total += board[i][j] == '.';
		}
	}
	REP( i, H )
	{
		REP( j, W - 1 )
		{
			if ( board[i][ j + 1 ] == '.' )
			{
				from_left[i][ j + 1 ] += from_left[i][j];
			}
		}
		for ( int j = W - 1; 0 < j; --j )
		{
			if ( board[i][ j - 1 ] == '.' )
			{
				from_right[i][ j - 1 ] += from_right[i][j];
			}
		}
	}
	REP( j, W )
	{
		REP( i, H - 1 )
		{
			if ( board[ i + 1 ][j] == '.' )
			{
				from_up[ i + 1 ][j] += from_up[i][j];
			}
		}
		for ( int i = H - 1; 0 < i; --i )
		{
			if ( board[ i - 1 ][j] == '.' )
			{
				from_down[ i - 1 ][j] += from_down[i][j];
			}
		}
	}

	LL res = 0;
	REP( i, H )
	{
		REP( j, W )
		{
			if ( board[i][j] == '#' )
			{
				continue;
			}

			const int k = from_left[i][j] + from_right[i][j] +
				from_up[i][j] + from_down[i][j] - 3;
			( res += ( mod_pow( 2, k, MOD ) + ( MOD - 1 ) % MOD ) *
			  mod_pow( 2, total - k, MOD ) ) %= MOD;
		}
	}
	cout << res << endl;

	return 0;
}