CodeTON5 G - Tenzing and Random Operations
https://codeforces.com/contest/1842/problem/G
Очень крутая задача!
К сожалению, ее я сам придумать не смог, пришлось прочитать разбор. В ней, кажется, если не думать вообще про мат. ожидание, а просто считать что (Ответ = Сумма / Кол-во Вариантов), то придумать решение будет сложно.
Единственное, что я знаю про мат. ожидание это то, что E(a*b) = E(a) * E(b) если a и b независимые числа, тут это и применяется.
Заведем n*m рандомных переменных, где x[i][j] - добавка к a[i] на j-ом ходе. x[i][j] либо 0, либо v.
Тогда ответ = мат ожидание произведения (a[i] + sum(x[i])).
Давайте постараемся решить для n=2, ответ = (a[0] + sum(x[0])) * (a[1] + sum(x[1])). Посмотрим на мат. ожидание x[0][j] * x[1][j] для какого-то j.
Можно сделать вывод, что мат. ожидание = x[0][j] * v. Понятно, что это обобщается и для большего кол-ва индексов.
Теперь вспомним, что при разных a и b x[i][a] и x[i][b] это независимые друг от друга величины! Значит, нам достаточно посчитать мат ожидание произведения x_a и x_b и перемножить их.
Теперь хочется раскрыть скобки в нашем произведении (которое (a[i] + sum(x[i]))) и посчитать ответ.
Давайте тогда напишем dp[i][j] - мат ожидание ответа, когда мы рассмотрели первые i индексов, и среди них встретилось j различных x-ов (т.е. для x[_][k], считаем кол-во различных k-шек). Понятно, что j <= min(n, m), потому что в каждом индексе при раскрытии скобок мы выберем либо a[i], либо какой-то из уже добавленных x-ов, либо добавим ровно один.
Вот, из каждого состояния dp у нас ровно 3 перехода (выбрать a[i], выбрать уже добавленный x <=> умножить на v, добавить новый x), и это достаточно просто пишется.
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, v;
cin >> n >> m >> v;
int inv = power(n);
vector dp(n + 1, vector<int>(n + 1));
dp[0][0] = 1;
for (int i = 1; i <= n; ++i) {
int a;
cin >> a;
for (int j = 0; j < i; ++j) {
dp[i][j + 1] = (dp[i][j + 1] + 1LL * dp[i - 1][j] * v % MOD * (m - j) % MOD * i % MOD * inv) % MOD;
dp[i][j] = (dp[i][j] + dp[i - 1][j] * (a + 1LL * j * v % MOD)) % MOD;
}
}
int ans = accumulate(dp[n].begin(), dp[n].end(), 0LL) % MOD;
cout << ans << '\n';
return 0;
}