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"; }
そんな苦戦しなかったけど細部を詰めるのに時間がかかった。