yukicoder : No.906 Y字グラフ

どうやるのが一番スムーズなんだろうな。
https://yukicoder.me/problems/no/906

問題

整数Nが与えられる。
N頂点の連結無向グラフのうち、次数3の点が1点で、残りの次数が2以下となるのは何通りか。

解法

次数3の点とそれに隣接する3点の計4点を固定すると、あとは(N-4)点を3つに分割する仕方を考えることになる。
以下X=N-4として、Xを順不同で3つに分けることを考える。

• 分割した結果、2つ以上の値が一致する場合
  • 一致する値をaとすると、残り1か所はX-2aで確定する。よってaは0≦2*a≦Xであるような整数を取りえるので、ceil((X+1)/2)通り
• 分割した結果、3つの値が不一致の場合
  • 最小値をaとすると、残り2値は(a+1)以上である。まずはこれだけを振り分けてしまうと、あとは(X-(3a+2))を2つに分けることになる。
  • これはceil((X-(3a+2)+1)/2)通りである。ceilが扱いにくいが、aの偶奇で分けると、それぞれ等差数列の総和を数える問題とみなせる。

ll H;
ll mo=1000000007;

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>>H;
	H-=4;
	
	ll ret=0;
	// 2same
	ret=(H/2+1)%mo;
	// all diff
	ll ma=(H-2)/3;
	ll a[2];
	a[0]=max(0LL,(H-1)/2);
	a[1]=max(0LL,(H-4)/2);
	FOR(i,2) if(a[i]>0) {
		ll b=a[i]/3+1;
		ll c=a[i]%3;
		ret+=c*(b%mo);
		ret+=3*(b%mo)*((b-1)%mo)%mo*(mo+1)/2%mo;;
	}
	
	cout<<ret%mo<<endl;
}

まとめ

妙に手間取った。