yukicoder : No.2793 Mancala Master

この式変形はしんどい…。
https://yukicoder.me/problems/no/2793

問題

N要素の正整数列Aと、整数Kが与えられる。
i=N～1と降順に、以下を行う。

初期状態で得られるスコアは1である。
A[i]を、A[0]～A[i-1]に整数個ずつ振り分ける。
もしA[i]→A[j]に振り分ける個数がmなら、取得スコアが(K^m-K^(m-1))倍される。

全振り分けパターンにおける、スコアの合計を求めよ。

解法

になることが帰納法で示せるというが…。
そもそもこの式をどう導けばいいんだ。

int T,N;
ll A[202020],K;
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>>T;
	while(T--) {
		cin>>N>>K;
		ll ret=1;
		ll sum=0;
		FOR(i,N) {
			cin>>A[i];
			sum+=1LL*(i+1)*(A[i]-1);
			ret=ret*(modpow(K,i+1)-1)%mo;
		}
		ret=ret*modpow(K,sum)%mo;
		cout<<ret<<endl;
	}
}

まとめ

出題者自身苦労して導いたようだけども。