F 到底是多少分啊

设最终第 $ii$ 项的值为 $a_i+x_{i}a\_i+x\_i$，也就是说第 $ii$ 项的值加了 $x_{i}x\_i$，那么由题意可知 $\sum x_i=t\backslash sum\; x\_i\; =\; t$。

最终的期望 $E=\frac{\sum _{x_1+x_2+\cdots +x_n=t}{\prod }_{i=1}^n(a_i+x_i)}{num}E=\backslash frac\{\backslash sum\backslash limits\_\{x\_1+x\_2+\backslash cdots+x\_n=t\}\backslash prod\backslash limits\_\{i=1\}^n(a\_i+x\_i)\}\{num\}$，其中 $numnum$ 为 $x_1+x_2+\cdots +x_n=tx\_1+x\_2+\backslash cdots+x\_n=t$ 不同解的个数。

令 $d{p}_{i,j}=\sum _{x_1+x_2+\cdots +x_i=j}{\prod }_{k=1}^i(a_k+x_k)dp\_\{i,j\}=\backslash sum\backslash limits\_\{x\_1+x\_2+\backslash cdots+x\_i=j\}\backslash prod\backslash limits\_\{k=1\}^i(a\_k+x\_k)$，那么枚举第 $ii$ 项加了几个 $11$，可以得到 $d{p}_{i,j}={\sum }_{k=0}^{j}d{p}_{i-1,j-k}\times (a_i+k)dp\_\{i,j\}=\backslash sum\backslash limits\_\{k=0\}^jdp\_\{i-1,j-k\}\backslash times(a\_i+k)$。

这个转移方程的复杂度是 $O(n{t}^2)\mathrm{的}\mathrm{，}\mathrm{考}\mathrm{虑}\mathrm{优}\mathrm{化}\mathrm{。}O(nt^2)\; 的，考虑优化。$

这显然可以NTT

将转移方程拆开，发现我们只需要快速计算 $\sum k\times d{p}_{i-1,j-k}\backslash sum\; k\backslash times\; dp\_\{i-1,j-k\}$ 即可，因为用前缀和容易维护 $\sum a_i\times d{p}_{i-1,j-k}\backslash sum\; a\_i\backslash times\; dp\_\{i-1,j-k\}$ 。

观察 $j\to j+1j\; \backslash rightarrow\; j+1$ 和式的变化。

$j:0\times d{p}_{i-1,j}+1\times d{p}_{i-1,j-1}+2\times d{p}_{i-1,j-2}+\cdots +j\times d{p}_{i-1,0}j:0\backslash times\; dp\_\{i-1,j\}+1\backslash times\; dp\_\{i-1,j-1\}+2\backslash times\; dp\_\{i-1,j-2\}+\backslash cdots+j\backslash times\; dp\_\{i-1,0\}$

$j+1:0\times d{p}_{i-1,j+1}+1\times d{p}_{i-1,j}+2\times d{p}_{i-1,j-1}+\cdots +(j+1)\times d{p}_{i-1,0}j+1:0\backslash times\; dp\_\{i-1,j+1\}+1\backslash times\; dp\_\{i-1,j\}+2\backslash times\; dp\_\{i-1,j-1\}+\backslash cdots+(j+1)\backslash times\; dp\_\{i-1,0\}$

显然下面的那个式子比上面那个式子多了 $d{p}_{i-1,j}+d{p}_{i-1,j-1}+\cdots +d{p}_{i-1,0}dp\_\{i-1,j\}+dp\_\{i-1,j-1\}+\backslash cdots+dp\_\{i-1,0\}$ 。

于是也能用前缀和维护。

这样期望的分子部分已经计算完毕了，至于分母的那个 $numnum$，是一个经典的整数拆分问题，就不过多赘述了，有很多的方法能去做，代码里面用的依然是 $dpdp$ 的思想。

时间复杂度：$O(nt)O(nt)$

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int maxn = 1e5 + 10;
#define __cs() int T; cin >> T; while (T--)
#define endl '\n'
ll qpow(ll a, int b, ll ans = 1) { for (; b; (a *= a) %= mod, b >>= 1)if (b & 1)(ans *= a) %= mod; return ans; }
ll n, t, a[3005], dp[3005][3005], num[3005][3005];
void solve() {
    scanf("%lld%lld", &n, &t);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &a[i]);
    }
    dp[0][0] = num[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        ll sum = 0, pre = 0, all = 0;
        for (int j = 0; j <= t; ++j) {
            (pre += dp[i - 1][j]) %= mod;
            (all += num[i - 1][j]) %= mod;
            dp[i][j] = (a[i] * pre + sum) % mod;
            num[i][j] = all;
            (sum += pre) %= mod;
        }
    }
    printf("%lld\n", dp[n][t] * qpow(num[n][t], mod - 2) % mod);
}
int main() {
    solve();
    return 0;
}