「CGOI-2」No will to break

一场战斗由 $n$ 个时刻组成，第 $i$ 个时刻有 $\frac{x_i}{x_i+y_i}$ 的概率是安全的。 在安全的时刻，你可以进行“聚集”。要求每连续的 $a$ 个时刻都至少要有 $b$ 个时刻进行聚集，在此前提下希望进行聚集的时刻数量尽量少；若不能满足此前提则认为进行聚集的时刻数量为 $0$。求进行聚集的时刻数量的期望，答案对 $998244353$ 取模。 ## Input 第一行输入三个整数 $n,a,b$，含义如上所述。 接下来 $n$ 行，第 $(i+1)$ 行输入两个整数 $x_i,y_i$，表示第 $i$ 个时刻有 $\frac{x_i}{x_i+y_i}$ 的概率是安全的。 ## Output 输出一个整数，表示期望对 $998244353$ 取模的值。 [samples] ## Background -传播-由-缺失-它们-子民-思想-哦-思想-信念- -它们-途径-缺失-切除-哦-虚空-全部-多样性- -同族-内部-意志-缺失-容器-永远-屈服-哦- -放-入-物质-全部-缺失-噫-空洞-壳-封印- ## Note ### 样例说明： 用 `1` 表示当前时刻是安全的，`0` 表示不是。 对于样例一，安全性序列只能是 `11111`，每连续三个时刻至少要有一个时刻用来聚集，可以选择第 $3$ 个时刻聚集，满足条件。聚集时刻数量为 $1$，可以证明不会小于 $1$。只有一种可能性，故期望也为 $1$。 对于样例二，安全性序列为 `100`，`101`，`110`，`111` 的概率相等，均为 $\frac14$，聚集时刻数量分别为 $0,2,1,1$，期望为 $\frac{0+2+1+1}4=1$。 --- ### 数据范围： **本题采用捆绑测试。** | 编号| 限制 | 分数 | | :-: | :-: | :-: | | 0 | $n\le20$ | 10pts | | 1 | $\forall i$，$x_i=0$ 或 $y_i=0$ | 10pts | | 2 | $n\le3\times 10^3$ | 30pts | | 3 | 无 | 50pts | 对于 $100\%$ 的数据，$1<n\le1.5\times10^4$，$1\le b<a\le\min(n,9)$，$x_i,y_i\ge0$，$0<x_i+y_i<998244353$。