yukicoder : No.2367 Painting Gascket

ちょっと手間取った。
https://yukicoder.me/problems/no/2367

問題

整数K,Nが与えられる。
レベルKのガスケット内の各三角形をN色のいずれかで塗る。
辺を共有する三角形が互いに同じ色とならない塗り方は何通りか。

解法

f(K,P) := レベルKのガスケットのうち、外周の3辺の塗り方のパターンがPの時の塗り方
とする。Pは以下のいずれか。

• 3辺とも未彩色
• 1辺彩色済み
• 2辺同じ色で彩色済み
• 3辺同じ色で彩色済み
• 2辺異なる色で彩色済み
• 3辺を2色で彩色済み
• 3辺を3色で彩色済み

Kの大きい順に色を定めて行こう。最終的にK=0の時に、三角形の塗り方はPの状況で定まる。

int K,N;
const ll mo=1000000007;

ll memo[101010][8];

ll hoge(int K,int pat) {
	if(K==0) {
		if(pat==0) return N;
		if(pat==1||pat==2||pat==3) return N-1;
		if(pat==4||pat==5) return N-2;
		return N-3;
	}
	if(memo[K][pat]>=0) return memo[K][pat];
	
	ll ret=0;
	if(pat==0) {
		ret=N*hoge(K-1,1)%mo*hoge(K-1,1)%mo*hoge(K-1,1)%mo;     // *** -> X**,X**,X**
	}
	if(pat==1) {
		ret=(N-1)*hoge(K-1,4)%mo*hoge(K-1,4)%mo*hoge(K-1,1)%mo; // A** -> AX*,AX*,X**
		ret+=hoge(K-1,2)%mo*hoge(K-1,2)%mo*hoge(K-1,1)%mo;      // A** -> AA*,AA*,A**
	}
	if(pat==2) {
		ret=(N-1)*hoge(K-1,5)%mo*hoge(K-1,4)%mo*hoge(K-1,4)%mo; // AA* -> AAX,AX*,AX*
		ret+=hoge(K-1,3)%mo*hoge(K-1,2)%mo*hoge(K-1,2)%mo;      // AA* -> AAA,AA*,AA*
	}
	if(pat==3) {
		ret=(N-1)*hoge(K-1,5)%mo*hoge(K-1,5)%mo*hoge(K-1,5)%mo; // AAA -> AAX,AAX,AAX
		ret+=hoge(K-1,3)%mo*hoge(K-1,3)%mo*hoge(K-1,3)%mo;      // AAA -> AAA,AAA,AAA
	}
	if(pat==4) {
		ret=(N-2)*hoge(K-1,6)%mo*hoge(K-1,4)%mo*hoge(K-1,4)%mo; // AB* -> ABX,AX*,BX*
		ret+=2*hoge(K-1,5)%mo*hoge(K-1,2)%mo*hoge(K-1,4)%mo;    // AB* -> AAB,AA*,AB*
	}
	if(pat==5) {
		ret=(N-2)*hoge(K-1,6)%mo*hoge(K-1,6)%mo*hoge(K-1,5)%mo; // ABB -> ABX,ABX,BBX
		ret+=hoge(K-1,5)%mo*hoge(K-1,5)%mo*hoge(K-1,5)%mo;      // ABB -> AAB,AAB,ABB
		ret+=hoge(K-1,3)%mo*hoge(K-1,5)%mo*hoge(K-1,5)%mo;      // ABB -> ABB,ABB,BBB
	}
	if(pat==6) {
		ret=(N-3)*hoge(K-1,6)%mo*hoge(K-1,6)%mo*hoge(K-1,6)%mo; // ABC -> ABX,BCX,ACX
		ret+=3*hoge(K-1,5)%mo*hoge(K-1,5)%mo*hoge(K-1,6)%mo;    // ABC -> AAB,ABC,AAC
	}
	
	return memo[K][pat]=ret%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>K>>N;
	if(N==1) {
		cout<<(K==0)<<endl;
		return;
	}
	if(N==2) {
		cout<<2<<endl;
		return;
	}
	MINUS(memo);
	cout<<hoge(K,0)<<endl;
}

まとめ

細かいところでミスしそう。