ヘクトのメモ

なんとなくいろいろ書いていくと思います.

ARC 037 D

ARC 037に参加した.
A,B,Cはすんなり解けたけど,Dは歯が立たず.
コンテスト後に解説スライドと他人のソースコードを見て解答.


問題文
http://arc037.contest.atcoder.jp/tasks/arc037_d

解法
レベルLのガスケットに含まれる単純多角形の数をf(L),
レベルLのガスケットの左下から上を経由しないで右下へ行く組み合わせの数をg(L),
レベルLのガスケットの左下から上を経由して右下へ行く組み合わせの数をh(L)
と定義する.

そうすると,f(L)の組み合わせ数は
レベルL-1のガスケットを3つ含んでいるので,3*f(L-1)
レベルL-1のガスケットの左下から右下に行くものを3つ組み合わせて(g(L-1)+h(L-1))^3
よって,f(L)=3*f(L-1)+(g(L-1)+h(L-1))^3

次に,g(L)の組み合わせ数は
レベルLのガスケットの中央を含まない時,
左下→中央下→右下なので
レベルL-1のガスケットの左下から右下に行くもの2つ組み合わせる.
よって,(g(L-1)+h(L-1))^2通り

レベルLのガスケットの中央を含む時,
レベルLの左下のレベルL-1のガスケットについて,左下から上に行く.
レベルLの上のレベルL-1のガスケットについて,左下から上を経由せずに右下に行く.
レベルLの右下のレベルL-1のガスケットについて,上から右下に行く.
ただし,レベルLのガスケットの中央の下の部分は一度しか通ってはいけない.
よって,( ( g(L-1)+h(L-1) )^2-h(L-1)^2)*g(L-1)

したがってg(L)=(g(L-1)+h(L-1))^2+((g(L-1)+h(L-1)^2-h(L-1)^2)*g(L-1)

最後に,h(L)の組み合わせ数は
レベルLのガスケットの中央を含むのみ時を考える.
レベルLの左下のレベルL-1のガスケットについて,左下から上に行く.
レベルLの上のレベルL-1のガスケットについて,左下から上を経由してに右下に行く.
レベルLの右下のレベルL-1のガスケットについて,上から右下に行く.
ただし,レベルLのガスケットの中央の下の部分は一度しか通ってはいけない.
よって,h(L)=((g(L-1)+h(L-1)^2-h(L-1)^2)*h(L-1)

よって,f,g,hの3つの漸化式を計算していけばよい.
初期値であるレベル0の時は,三角形1個より f(0)=1
三角形の左下→右下の経路よりg(0)=1
三角形の左下→上→右下の経路よりh(0)=1

計算量はO(L)

以下はソースコード

const ll mod=1000000007;

ll f[100010],g[100010],h[100010];

int main(void){
	int L;
	cin >> L;
	f[0]=1LL,g[0]=1LL,h[0]=1LL;
	rep(i,L){
		ll gh=(g[i]+h[i])%mod;
		f[i+1]=3*f[i];
		f[i+1]+=gh*gh%mod*gh%mod;
		f[i+1]%=mod;

		g[i+1]+=gh*gh%mod;
		g[i+1]+=(gh*gh-h[i]*h[i]+mod)%mod*g[i]%mod;
		g[i+1]+=mod;
		g[i+1]%=mod;

		h[i+1]+=(gh*gh-h[i]*h[i]+mod)%mod*h[i]%mod;
		h[i+1]+=mod;
		h[i+1]%=mod;
	}
	cout << f[L] << endl;
	return 0;
}