伏特找到了 skip 蚤，希望他负责建造月球车站。然而众所周知，skip 蚤是一只大鸽子。于是他掏出了口袋里的硬币，在桌面上摆成了一排，要伏特和他玩一局游戏，结束后就开始干活。
初始时每枚硬币要么正面朝上，要么背面朝上。游戏会一轮轮进行，如果某一时刻（包括初始时刻）所有硬币都是正面，则游戏立刻结束。
每轮的操作如下：
取出最左侧的硬币。
如果这枚硬币正面朝上，则由 skip 蚤选择是否翻转，否则由伏特选择是否翻转。
将这枚硬币放到最右边。
伏特已经被铁路建造弄昏了头，于是他决定随机翻转。每次轮到他决定时，他选择翻转的概率为 $p$，选择不翻转的概率为 $1-p$，不同轮之间独立。
skip 蚤是一只非常聪明的鸽子，他通过神秘手段知道了伏特的策略，并且他将以最优策略决定是否翻转来使游戏期望进行轮数尽可能大。
求游戏期望进行几轮，答案对 $998244353$ 取模。
有个 max，非常难做。
一个神奇的入手角度：考虑双方都绝顶聪明的时候，会是什么情况。
设现在为 \(s\)，那么如果上一步走的人如果是 skip，那么如果这个状态是第二次访问，他可以入队。如果上一步走的人是伏特，那么当这个状态是第一次访问，它可以入队。这样可以求出双方绝顶聪明的答案。
由于扩展出的两种状态只差一个数，所以他们要不都是第一次，要不都是第二次，所以每次扩展最多扩展一个数。同时可以证明所有状态都可以到达最终态，所以图是形成一条链的时候。那么之后描述第 \(i\) 个状态指在那个链中排名第 \(i\) 的状态。
回到原题，那么 skip 在第 \(i\) 个状态时一定是往 \(i-1\) 走的，伏特则有概率到 \(i-1\)，有概率到 \(x>i-1\)，那么定义 \(dp_i\) 表示从 \(i\) 到 \(i-1\) 期望要走多少步，设 \(c\) 为走到 \(i-1\) 的概率，那么 \(dp_i=(1-c)\sum\limits_{j=i}^xdp_j+c\)。预处理 \(dp\) 的后缀和 \(s\).
\(cdp_i=(1-c)(s_{i+1}-s_{x+1})+1\)，解方程就行了。
复杂度 \(O(2^n)\)，要特判 \(a=0\) 和 \(b=0\)。
#include<bits/stdc++.h>
using namespace std;
const int P=998244353,N=25,M=1<<23;
char str[N];
int s,p,q[M],t[M],a,b,n,l,r,c[M],ans,ivp,ivfp;
int pown(int x,int y)
{
if(!y)
return 1;
int t=pown(x,y>>1);
if(y&1)
return 1LL*t*t%P*x%P;
return 1LL*t*t%P;
}
int main()
{
scanf("%s%d%d",str,&a,&b);
n=strlen(str);
for(int i=0;str[i];i++)
s=s<<1|str[i]-48;
if(!a)
return puts(s==(1<<n)-1? "0":"-1"),0;
if(!b)
{
int c=1;
for(int i=1;str[i];i++)
if(str[i]^str[i-1])
++c;
if(c>2)
return puts("-1"),0;
if(c==2&&n>1&&str[0]==str[1]&&str[0]=='1')
return puts("-1"),0;
}
p=1LL*a*pown(a+b,P-2)%P;
q[l=r=1]=(1<<n)-1;
c[q[1]]=2;
while(l<=r)
{
t[q[l]]=l;
c[q[l]>>1]++,c[q[l]>>1|1<<n-1]++;
if(c[q[l]>>1]==1)
q[++r]=q[l]>>1;
if(c[q[l]>>1|1<<n-1]==2)
q[++r]=q[l]>>1|1<<n-1;
++l;
}
ivfp=pown(P+1-p,P-2),ivp=pown(p,P-2);
for(int i=r,dp;i>1;i--)
{
if(q[i]>>n-1)
dp=1;
else
{
int a=ivfp,b=t[q[i-1]^1];
if(q[i-1]&1)
a=ivp;
dp=(c[i+1]-c[b+1]+1+P)*1LL*(a+P-1)%P+1;
}
c[i]=(c[i+1]+dp)%P;
if(i<=t[s])
(ans+=dp)%=P;
}
printf("%d",ans);
}