题目描述
形式化题面
意识流题面与形式化题面无关,有空的话可以去鉴赏。
给定一个长度为 n 的 01 串 b,若存在一个 n 的排列 a,满足:对于 ai(2≤i≤n),记 m=maxj=1i−1{aj},
- 若 bi=1,则 ai>m;
- 否则 ai<m。
则称 a 为 b 的一个「PBS (Permutation and Binary String) 排列」,注意到 b1 的取值是任意的,对 a 没有影响。
现在,小 B 想知道,对于给定的 b,存在多少个它的「PBS 排列」。
由于结果可能很大,所以你只需要输出结果对 998244353 取模的值。
意识流题面
从 1 开始,足迹遍及整个长度为 n 的 01 序列 b,心也随之逐渐踏过长度也为 n 的排列 a。
记当前经过位置的下标为 i。
你初始有一值 m=m0=NaN,你可以认为 ∀x∈R,x>m0,x<m0 均成立。
进行一个最大值的比较。心的每次跃进,即 i←i+1,都会自动进行 m←max(m,ai−1)。但如果 i=2,直接进行 m←ai−1。
自然地引出下面的法则:
若 bi=1,则 ai>m;否则 ai<m。
如果不符合这样的法则,那么视作心已然不合乎你的足迹,将会坠落。
你自然期待千年后依旧璀璨,永不坠落,请回答:
记「不会让你坠落的排列 a」为一个「PBS 排列」。你想知道对于 b,存在多少个「PBS 排列」。注意到 b1 的取值是任意的,对 a 没有影响。
由于结果可能很大,所以你只需要输出结果对 998244353 取模的值。
样例
3
3
111
3
101
4
0101
1
1
2
样例说明
- 对于数据 1,唯一的 a={1,2,3}。
- 对于数据 2,唯一的 a={2,1,3}。
- 对于数据 3,存在两个不同的 a:a={1,3,2,4} 或 a={2,3,1,4}。
提示
对于 100% 的数据,有 1≤T≤104,2≤n≤106,∀i∈[1,n],bi∈{0,1}。
保证单个测试点内 ∑n≤2×106。