Codeforces #858 : Div2 D. DSU Master

Div2 6問回なのに4問目の難易度が妙に高かった回。
https://codeforces.com/contest/1806/problem/D

問題

01で構成される(N-1)要素の整数列Aが与えられる。

m-1要素の順列Pを考える。
以下の手順で、m頂点のグラフを作ることを考える。
以下の手順を進めていくと、弱連結成分毎に出次数0の点が1個ずつできる。
i回目の手順では、点P[i]が含まれる弱連結成分と点P[i]+1が含まれる弱連結成分のうち、それぞれ出次数0の点を考える。
この点をu,vとする。
A[P[i]]=0ならu→v、A[P[i]]=1ならv→uに有向辺を張る。

最終的なPのスコアは、(1-originで)頂点1番の入次数とする。
m=2～Nのそれぞれに対し、m!通りのPにおけるスコアの総和を求めよ。

解法

今P[i]の操作によって頂点1番の入次数が増えるには、A[P[i]]=0でないといけないし、その時点で点P[i]を含む弱連結成分の出次数0の点が1番でなければならない。
最初のi回の操作まで考えたとき、出次数0の点が1番である組み合わせf(i)は
f(i+1) = f(i)*(i-A[i])
となる。
これを踏まえて解g(m)は
g(m)=m*g(m-1)+(A[m]==0?F[m]:0)
となる。

int T,N;
int A[505050];
const ll mo=998244353;
ll F[505050];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		F[1]=1;
		FOR(i,N-1) {
			cin>>A[i];
			F[i+2]=F[i+1]*(i+1-A[i])%mo;
		}
		ll ret=0;
		for(i=1;i<=N-1;i++) {
			ret=(ret*i+((A[i-1]==0)?F[i]:0))%mo;
			cout<<ret<<" ";
		}
		cout<<endl;
	}
}

まとめ

コードは短いけど考察がちょっと大変。