AtCoder ARC #106 : F - Figures

こういう応用、ぱっと思い浮かばないな。
https://atcoder.jp/contests/arc106/tasks/arc106_f

問題

N個の部品からなるフィギュアを組み立てる。
各部品iにはD[i]個の穴がある。

ここに(N-1)個の接続用部品を使い、部品を連結させていく。
接続用部品では、2つの部品の穴を1つずつ選択してそこに差し込むことで部品を連結する。
当然、1つの穴は1つの接続用部品でしか使えない。

全部品が連結となるような連結のさせ方は何通りか。

解法

全域木の考え方を応用する。
各部品に代表穴を定めよう。以下、各連結部品に1つの代表穴がある状態を維持する。
この定め方の時点で、まずProd(D[i])通りある。
全穴数をSとする。
以後、以下の手順を(N-2)回繰り返す。

• 代表ではなく、未使用の穴を1つ選択する。i回目の選択では、(S-N+1-i)個の選択肢がある。
• その穴と、他の連結成分の代表穴を連結する。i回目の選択では、代表穴の選び方に(N-i)個の選択肢がある。

最後の1手だけは、残された2つの代表穴を連結する。

こうすると、順序込みで選び方は通りとなる。
順序を無視すると(N-1)!で割ることができ、結局解は。

int N;
int D[202020];
const ll mo=998244353;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll S=0;
	ll ret=1;
	FOR(i,N) {
		cin>>D[i];
		ret=ret*D[i]%mo;
		S+=D[i];
	}
	FOR(i,N-2) ret=ret*((S-N-i)%mo)%mo;
	cout<<ret<<endl;
}

まとめ

実装は短いんだよな。