CF369D Valera and Fools

在一个美好的早晨，$n$ 个“傻瓜”排成一排。之后，他们互相编号，从 $1$ 到 $n$，每人一个独一无二的编号。在游戏结束前，他们不会更改自己的编号。 每个“傻瓜”都有恰好 $k$ 发子弹和一把手枪。此外，第 $i$ 号傻瓜射击目标时，有 $p_i$ 的概率（百分比）能杀死目标。 傻瓜们决定进行若干轮“游戏”。每一轮游戏如下：每一个当前存活的傻瓜都同时向存活编号最小的另一个傻瓜开枪（傻瓜不会朝自己开枪）。所有射击在同一时间发生（即视为同时进行）。如果只剩下一个存活的傻瓜，他不会开枪。 我们将某一时刻所有活着的傻瓜的编号集合称为一个“情况”。如果存在一个整数 $j$（$0 \leq j \leq k$），并且在经过 $j$ 轮游戏后出现这种情况的概率大于零，我们就说这个“情况”是可能出现的。 Valera 知道 $p_1,p_2,\dots,p_n$ 和 $k$。请你帮 Valera 计算有多少种不同的可能情况。

第一行包含两个整数 $n,k$（$1 \leq n,k \leq 3000$）——最初的傻瓜人数以及每个人的子弹数量。 第二行包含 $n$ 个整数 $p_1,p_2,...,p_n$（$0 \leq p_i \leq 100$）——每个傻瓜的击杀概率（百分比）。

输出一个整数，表示答案，即共有多少种不同的可能情况。

在第一个样例中，除了 $ \{1,2\} $ 之外，所有情况都是可能的。 在第二个样例中，只有一个傻瓜，所以他不会开枪。 在第三个样例中，可能的情况是 $ \{1,2\} $（初始时）和“空”情况 $ \{\} $（经过一轮游戏后）。 在第四个样例中，唯一可能的情况是 $ \{1,2,3\} $。 由 ChatGPT 5 翻译