yukicoder : No.1165 Paint Squares

これ一度見たことあると一気に難易度下がるよね。
https://yukicoder.me/problems/no/1165

問題

P*Qのグリッドを4色に塗り分けたい。
その際、どの2*2の領域も4色が1回ずつ含まれる塗り方は何通りか。

解法

例えば左上端を

AB
CD

と塗ったとき、他の行・列がどうなるかを考える。
その際、取れる選択肢は以下のいずれかである。

• 各列内に現れる色は(A,C)・(B,D)が交互に繰り返される。3列目以降各列では、AとC、BとDどちらが先頭行に来るか選べる。
• 各行内に現れる色は(A,B)・(C,D)が交互に繰り返される。3行目以降各行では、AとB、CとDどちらが先頭列に来るか選べる。

なお、全体を左上のパターンを繰り返して塗りつぶす場合は、上記両方の条件に該当する。
そこで、左上端の塗り方が4!通りあることを考えると4!*(2^(P-2)+2^(Q-2)-1)が解。

ll P,Q;
const ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>P>>Q;
	ll ret=0;
	// yoko
	ll cur=24;
	for(i=3;i<=P;i++) cur=cur*2%mo;
	ret+=cur;
	cur=24;
	for(i=3;i<=Q;i++) cur=cur*2%mo;
	ret+=cur;
	ret+=mo-24;
	cout<<ret%mo<<endl;
}

まとめ

Codeforcesで似たようなの何度か見てる気が。