LNDS

注意，本题的 $p$ 是 $1$ 的概率，答案要 $\times 1000^n$。

期望题目

DP 数学 DFS

直接 DP!

不难发现，LNDS 是 形如 $0000011111$ 的状物，其中 $cnt_0 \ge 0 且 cnt_1 \ge 0$，即出现次数为正整数。

于是设 $dp_{i, j, k}$ 表示转移到 $i$，有 $j$ 个 $0$，答案（$len$ lnds）为 $k$ 的 概率,则转移显然。

如果 $a_i$ 是 $0$ 则 $dp_{i, j, k} \to dp_{i+1, j+1, \max(j+1, k)}$

否则，这是 $dp_{i, j, k} \to dp_{i+1, j, \max(j+1, k+1)}$。

注意我只描述了转移的点，不是具体的方程，具体只用*一下概率就可以了。