yukicoder : No.1348 Split Tile

このテクは過去にもどこかで使ったな。
https://yukicoder.me/problems/no/1348

問題

N個のタイルが横1列に並んでいる。
Xを以下のように定める。
タイルを1つ取り除き、そのつど連結成分の数をXに加算する、という処理をタイルがなくなるまでN回繰り返す。

タイルを取り除く手順N!通りにおけるXの総和を求めよ。

解法

連結成分の数を数える、というのを、「まだ残っているタイルのうち、左隣のタイルがない状態のものを数える」と言い換えよう。
そうすると、一番左のタイルを除けば、自身と左隣のタイルがどれほどの時間差で取り除かれるかだけ考えればよくなる。

よってその時間差を総当たりし、その時間差で両タイルが消えるパターンを数え上げよう。

ll N;
const ll mo=998244353;
ll fact[1010101];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	fact[0]=1;
	FOR(i,1010000) fact[i+1]=fact[i]*(i+1)%mo;
	
	cin>>N;
	ll ret=0;
	//端
	ret+=N*(N-1)/2%mo*fact[N-1];
	//それ以外
	for(i=2;i<=N;i++) {
		(ret+=(N-1)*(i-1)%mo*(N+1-i)%mo*fact[N-2])%=mo;
	}
	
	cout<<ret<<endl;
	
}

まとめ

この連結成分の数えあげを隣のマスが空であるマスの数え上げに言い換えるの、どこに使ったんだっけかな。