UOJ Logo Universal Online Judge

UOJ

#683. 【UR #22】月球车站

附件下载 统计

伏特找到了 skip 蚤,希望他负责建造月球车站。然而众所周知,skip 蚤是一只大鸽子。于是他掏出了口袋里的硬币,在桌面上摆成了一排,要伏特和他玩一局游戏,结束后就开始干活。

初始时每枚硬币要么正面朝上,要么背面朝上。游戏会一轮轮进行,如果某一时刻(包括初始时刻)所有硬币都是正面,则游戏立刻结束。

每轮的操作如下:

  1. 取出最左侧的硬币。

  2. 如果这枚硬币正面朝上,则由 skip 蚤选择是否翻转,否则由伏特选择是否翻转。

  3. 将这枚硬币放到最右边。

伏特已经被铁路建造弄昏了头,于是他决定随机翻转。每次轮到他决定时,他选择翻转的概率为 $p$,选择不翻转的概率为 $1-p$,不同轮之间独立。

skip 蚤是一只非常聪明的鸽子,他通过神秘手段知道了伏特的策略,并且他将以最优策略决定是否翻转来使游戏期望进行轮数尽可能大。

求游戏期望进行几轮,答案对 $998244353$ 取模。

输入格式

第一行一个长度为 $n$ 的 01 串,表示初始的硬币序列,0 表示硬币背面朝上,1 表示硬币正面朝上。

第二行两个整数 $a, b$,表示 $p=\frac{a}{a+b}$。

输出格式

输出一个整数,表示 skip 蚤在使用最优策略的情况下,游戏结束所需要的期望轮数。

如果游戏轮数的期望不收敛,则输出 $-1$。

否则,题目数据保证了该期望必定可以写成一个分数 $\frac{c}{d}$ ($c \ge 0, d \ge 1$),且分母 $d$ 不是 $998244353$ 的倍数。请输出一个整数 $x \in [0, 998244353)$ 使得 $dx$ 和 $c$ 在模 $998244353$ 意义下同余。

样例一

input

10
1 1

output

8

explanation

当局面为 10 时,skip 蚤会选择翻转变为 00

此时伏特有 $\frac 12$ 的概率翻转使局面变为 01,$\frac 12$ 的概率不翻转使局面不变,即期望两轮后局面变为 01

接下来伏特有 $\frac 12$ 的概率翻转使游戏结束,$\frac 12$ 的概率不翻转使局面重新变为 10

整体来看,局面为 10 时,期望经过四轮后,有$\frac 12$ 的概率游戏结束,$\frac 12$ 的概率局面重新变为 10。因此游戏期望进行轮数为 $8$ 轮。

样例二

input

0011
1 0

output

2

explanation

由于伏特一定会翻转背面硬币,所以两轮以后所有硬币都正面朝上了。

样例三

input

0101
1 0

output

-1

explanation

由于伏特会一直翻转,skip 蚤也只需一直翻转即可保证游戏不会结束。

样例四

见附件下载。

限制与约定

对于 $100\%$ 的数据,$1\leq n \leq 23$,$0\leq a, b \leq 998244352, 998244353\nmid a+b$。

子任务编号 $n\leq$ 特殊性质 分值
1 $23$ $a=0$ $5$
2 $b=0$ $10$
3 $4$ $a,b\leq 10$ $10$
4 $12$ $30$
5 $23$ $45$

时间限制:$\texttt{2s}$

空间限制:$\texttt{512MB}$

后记

由于 skip 蚤实在是太鸽了,愤怒的跳蚤国王把 skip 蚤抓回去煲成了汤。