CODE FESTIVAL 2017 Final,G: Mancala

https://cf17-final-open.contest.atcoder.jp/tasks/cf17_final_g

答えは(f(a)の期待値)*(K+1)^Nなのでf(a)の期待値を求めることにします。

まず最小値を達成する操作とはどのようなものなのか考えます。
i番目の値Aiについて最初からAi>iであれば何も操作を行えませんが、Ai<=iなら操作を保留しておいて、i以降で操作を行ったあと、Aiについて出来る限りやると言い換えても良いです。

なので、
dp(i,j):=(i,N]において操作がj回行われる確率
とすれば、期待値の線形性により
f(a)=ΣiΣjΣk G(i, j)*u(i,j,k+l)となります。
ただしu(i,j,s):=s%i(j<=i),s(j>i)です。

問題はjがどのくらい大きくなるかですが、ΣN/iと同じような計算になってO(NlogN)くらいだろうという予測が立ちます。
実際適当なコードで実験すればj<=2000とわかるので、O(2000*N*K)で間に合います。

int N, K;

ll dp[110][2000];
ll S[110];


ll mod_pow(ll a, ll n) {
	if(n == 0) return 1;
	ll res = mod_pow(a, n / 2);
	if(n % 2 == 0) return res * res % mod;
	else return a * res % mod * res % mod;
}


ll f(int i, int k, int s) {
	if(k <= i) return s % i;
	else return s;
}

void solve() {
	cin >> N >> K;
	dp[N][0] = 1;
	rer(i, N + 1, 2) {
		rep(j, 0, 2000) {
			if(!dp[i][j]) continue;
			rep(k, 0, K + 1) {
				if(k <= i) {
					ADD(dp[i - 1][j + (j + k) / i], dp[i][j]);
				}
				else ADD(dp[i - 1][j], dp[i][j]);
			}
		}
	}
	rep(i, 1, N + 1) {
		rep(j, 0, 2000) {
			if(!dp[i][j]) continue;
			rep(k, 0, K + 1) {
				ADD(S[i], dp[i][j] * f(i, k, j + k) % mod);
			}
		}
	}
	ll ans = 0;
	rep(i, 1, N + 1) ADD(ans, S[i] * mod_pow(K + 1, i - 1) % mod);
	cout << ans << "\n";
}

そんな苦戦しなかったけど細部を詰めるのに時間がかかった。