AtCoder ABC #284 : G - Only Once

こちらは自力で解けた。
https://atcoder.jp/contests/abc284/tasks/abc284_g

問題

各要素1～Nの値を取る、N要素の整数列AはN^N通りある。
f(A)を以下の通り定義する。
i＝1～Nに対し、i,A[i],A[A[i]].....と並べたとき、(i1つごとに)1回しか現れない値の個数の総和

A全パターンにおけるf(A)の総和を求めよ。

解法

i, A[i], A[A[i]],....という数列はあるところで閉路に入る。
上記数列のユニークな要素数をX、うち閉路に入るまでの要素数をYとする。
対称性より、Y=0…(X-1)が同じバリエーションだけありうる。

上記をもとに、Xを総当たりしながら、その組み合わせの総和を計算していこう。

ll N,mo;

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>>mo;
	ll ret=0;
	ll pat=1;
	for(i=0;i<=N-1;i++) {
		ll oth=modpow(N,N-1-i);
		(ret+=pat*oth%mo*(1LL*i*(i+1)/2%mo))%=mo;
		pat=pat*(N-1-i)%mo;
	}
	cout<<ret*N%mo<<endl;
}

まとめ

思いつけて良かったね。