Readme

2954.Count-the-Number-of-Infection-Sequences

对于两个相邻sick点之间的区间，他们被感染的次序看似很复杂，其实无非就是“感染左端点”和“感染右端点”两个选择里的随机选取。因此任意一个感染序列，都对应了一种LR的二值序列。假设区间内未被感染的点有m个，那么感染过程的序列种类（即排列）就是2^(m-1)。为什么是m-1？因为当只剩最后一个未感染点时，“感染左端点”和“感染右端点”这两个选择对应是同一个点。

此外需要注意，如果只有单边存在sick的区间（比如第一个区间或者最后一个区间），它的序列种类只有1.

以上是一个区间的种类数。那么如何计算所有点的总的序列种类呢？假设前述的区间m1,m2,...mk的总数是n，那么这n个点的随机排列是n!种。但是，对于属于某个特定区间的点而言（比如说属于第k个区间的mk个点），它的顺序不应该是完全随机的，随意我们要再除以mk的阶乘抵消这种随机性。但是属于第k区间的点肯定也不是只有一种排列，而是有2^(mk-1)种方法（如果是单边存在sick的区间，那就只是1种），故需要再乘以该区间内点的排列数。

所以这道题的答案是

ret = n!;
for (int i=0; i<k; i++)
  ret = ret / mi! * (2^mi);

注意到其中涉及到除法，想要保持同余操作的正确性，我们必须将除以m!的操作，转化为乘以m!的（关于1e9+7取余的）逆元的操作。我们可以利用小费马定理：inv(a) ≡ a ^ (M-2) (mod M) 通过快速幂实现。