yukicoder : No.3551 Regions by Random Points 2

これもすんなり解けて良かったね。
https://yukicoder.me/problems/no/3551

問題

整数Nが与えられる。
円があり、以下の処理をN回行う。

• 円周のランダムな位置を２点選び、間を線分で結ぶ。

これらN本の線分で分割される、領域の個数の期待値を求めよ。

解法

もしN本の線が互いに交差しない場合、解はN+1である。
そのうえで、ある２本の線が交差する確率は、それらを成す４点の並びを考えると1/3である。
よって解はN+1+C(N,2)/3となる。

ll N;
const ll mo=998244353;

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;
	ll a=N+1+1LL*N*(N-1)/2%mo*modpow(3)%mo;
	cout<<a%mo<<endl;
}

まとめ

★3にしてはコードが短く済む。