好像和题解不太一样。
令 \(f_{i,j}\) 为第 \(j\) 秒末识别出第 \(i\) 首歌的概率。那么答案就是 \(\sum\limits_{i=1}^n\sum\limits_{j=1}^Tf_{i,j}\)。
转移分两种：
- 听完了这首歌都没识别出，此时算是识别出这首歌了，\(f_{i,j}\gets f_{i-1,j-t_i}\cdot (1-p_i)^{t_i}\)。
- 听到一半识别出了，假设听到第 \(k\) 秒末识别出来，\(f_{i,j}\gets f_{i-1,j-k}\cdot p_i\cdot (1-p_i)^{k-1}\)。
那么：
\[f_{i,j}=f_{i-1,j-t_i}\cdot (1-p_i)^{t_i}+\sum\limits_{k=1}^{t_i}f_{i-1,j-k}\cdot p_i\cdot (1-p_i)^{k-1}
\]
朴素转移是 \(O(nT^2)/O(nT^2\log T)\) 的，考虑优化。
发现 \(f_{i,j}\) 的转移是一个多项式点值的形式。对于固定的 \(i\) 不同的 \(j\)，多项式的系数是类似的。于是考虑如何从 \(f_{i,j-1}\) 推到 \(f_{i,j}\)。
具体地，令：
\[g_{i,j}=\sum\limits_{k=1}^{t_i}(1-p_i)^{k-1}f_{i-1,j-k}
\]
则：
\[f_{i,j}=f_{i-1,j-t_i}\cdot (1-p_i)^{t_i}+p_i\cdot g_{i,j}
\]
于是只需要考虑如何从 \(f_{i,j-1},g_{i,j-1}\) 推出 \(g_{i,j}\)：
\[\begin{aligned}g_{i,j-1}&=\sum\limits_{k=1}^{t_i}(1-p_i)^{k-1}f_{i-1,j-k-1}\\&=\sum\limits_{k=2}^{t_i+1}(1-p_i)^{k-2}f_{i-1,j-k}\end{aligned}
\]
比较 \(g_{i,j}\) 与 \(g_{i,j-1}\) 中 \(f_{i-1,j-k}\) 的系数，令：
\[F(k)=(1-p_i)^{k-2}f_{i-1,j-k}
\]
则：
\[g_{i,j}=(1-p_i)(g_{i,j-1}-F(t_i+1))+f_{i-1,j-1}
\]
于是直接 \(O(nT\log T)\) 递推即可。可能需要滚动数组。
typedef double db;
const int N = 5e3 + 500;
int n, m, t[N];
db p[N], f[2][N], g[2][N];
db qpow(db p, int q) {
db res = 1, fl = (q >= 0);
if (q < 0) q = -q;
for (; q; q >>= 1, p *= p)
if (q & 1) res *= p;
if (!fl) res = 1. / res;
return res;
}
db F(int i, int j, int k) {
if (k > j) return 0;
return qpow(1 - p[i], k - 2) * g[i & 1 ^ 1][j - k];
}
int main() {
n = rd(), m = rd(), f[0][0] = 1;
for (int i = 1; i <= n; i++)
p[i] = rd(), t[i] = rd(), p[i] /= 100;
db res = 0;
for (int i = 1, op = 1; i <= n; i++, op ^= 1) {
for (int j = 0; j <= m; j++) f[op][j] = g[op][j] = 0;
for (int j = 1; j <= m; j++) {
db tp = g[op][j - 1] - F(i, j, t[i] + 1);
g[op][j] = tp * (1 - p[i]) + f[op ^ 1][j - 1];
f[op][j] = p[i] * g[op][j];
if (j >= t[i]) f[op][j] += f[op ^ 1][j - t[i]] * qpow(1 - p[i], t[i]);
res += f[op][j];
}
}
printf("%.9lf", res);
return 0;
}