yukicoder : No.2668 Trees on Graph Paper

なるほど。
https://yukicoder.me/problems/no/2668

問題

整数Nが与えられる。
2次元座標上で、x座標とy座標がいずれも正整数であり、かつ和が偶数で2N以下である格子点を考える。
それらの間を辺でつなぐことを考える。
ただし取れる辺は(x,y)-(x+2,y)か(x,y)-(x+1,y+1)か(x,y)-(x,y+2)を結ぶものである。

こうしてできる全域木全通りについて、次数が1の点のX座標の積の和を求めよ。

解法

レベルnの頂点とは、(x+y)/2がnである点の集合とする。
レベルnの頂点はそれぞれ1つのレベルn-1と辺を結ぶ。
このことから、レベルnの頂点がそれぞれ次数1になるかどうかは、レベルn+1との頂点の辺の結び方による。

ここで、レベルnの頂点について、次数が1の点のX座標の積の和を考える。
レベルnの点(x,y)から(x+1,y+1)に辺を伸ばしているようなレベルn+1の点を赤く塗り、残りを白く塗る。

レベルnのうち赤く塗った点の間に白く塗った点があるが、それぞれ(x,y)から(x+2,y)に辺を伸ばすケースと(x,y)から(x,y+2)に伸ばすケースで変が貼られる白点が連続する。
その切り替わりが起きるタイミングで、レベルnの点に次数1の点が2つ発生する。

レベルの各点を端から見ると赤点 → 0個以上の白点 → 切り替わり →0個以上の白点 → 赤点 → ・・・・という風に遷移するので、これをDPで数え上げよう。
切り替わりの前後ではX座標の値の積を取るようにする。

ll N;
ll mo;

ll dp[10101010][2][2];

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>mo;
	
	dp[0][0][1]=1;
	for(i=1;i<10001010;i++) {
		//赤→四角→赤
		dp[i][1][0]+=dp[i-1][1][0];
		//赤→四角→白
		dp[i][0][1]+=i*dp[i-1][1][0];
		//白→四角→白
		dp[i][0][1]+=i*dp[i-1][0][0]%mo*(i-1);
		//白→四角→赤
		dp[i][1][0]+=dp[i-1][0][0]%mo*(i-1);

		//赤→白
		dp[i][0][0]+=dp[i-1][1][0];
		//白→白
		dp[i][0][0]+=dp[i-1][0][0];
		dp[i][0][1]+=dp[i-1][0][1];
		//白→赤
		dp[i][1][0]+=dp[i-1][0][1];
		
		dp[i][0][0]%=mo;
		dp[i][1][0]%=mo;
		dp[i][0][1]%=mo;
		dp[i][1][1]%=mo;
	}
	
	ll p2=0,p3=0;
	
	ll ret=1;
	
	for(i=2;i<N;i++) {
		(ret*=(dp[i*2-1][0][0]+dp[i*2-1][1][0]))%=mo;
	}
	for(i=1;i<=2*N-1;i++) ret=ret*i%mo;
	
	cout<<ret<<endl;
	
}

まとめ

二項係数に行ってしまい失敗した。