正解
思考的时候没有得到除了高斯消元以外的思路……
原来是一道板子题……
设(p_i)为选(i)的概率，(e_i)为(i)第一次变成(0)的期望步数（显然和(0)第一次变成(i)一样）
显然可以列出式子：
(e_i=1+sum p_je_{iigoplus j})
(e_0=0)
用集合幂级数来表示(e)和(p)，分别记为(E)和(P)。
乘法定义为异或运算。
于是有(E+c=I+P*E)
(I)表示全部位置都是(1)的集合幂级数。
(c)是用来修正(E_0)的常数。
“集合幂级数”只是个高大上的名词……
类似于多项式，一个集合幂级数表示成这个样子：(F=sum a_ix^i)
和多项式不同的是，这里按照需要定义了(x^a*x^b)的结果。比如，如果乘法定义为异或，那么(x^a*x^b=x^{a igoplus b})
设(S(F))表示(sum F_i)
于是有(S(E)+c=2^n+S(P)S(E))
(S(P*E)=S(P)S(E))
因为(P)中每个数和(E)中每个数都可以做出贡献。
由于(S(P)=1)，所以(c=2^n)
所以(E+2^n=I+P*E)
移项得(2^n-I=(P-1)*E)
做(FWT)得(FWT(2^n-I)=FWT(P-1)FWT(E))
考虑计算(FWT(E)_i)。可以只有(i=0)时(FWT(P-1)=0)。
(i>0)时就暴力算出，(i=0)时根据(E_0=0)手玩出(FWT(E)_0)的取值。
算出(FWT(E))之后(IFWT)回去即可。
代码
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 18
#define ll long long
#define mo 998244353
ll qpow(ll x,int y=mo-2){
ll r=1;
for (;y;y>>=1,x=x*x%mo)
if (y&1)
r=r*x%mo;
return r;
}
int n;
int a[1<<N],p[1<<N],e[1<<N],f[1<<N];
void fwt(int F[]){
for (int i=1;i<1<<n;i<<=1)
for (int j=0;j<1<<n;j+=i<<1)
for (int k=j;k<j+i;++k){
int x=F[k],y=F[k+i];
F[k]=(x+y)%mo;
F[k+i]=(x-y+mo)%mo;
}
}
int main(){
scanf("%d",&n);
ll sum=0;
for (int i=0;i<1<<n;++i)
scanf("%d",&a[i]),sum+=a[i];
sum=qpow(sum);
for (int i=0;i<1<<n;++i)
p[i]=a[i]*sum%mo;
for (int i=0;i<1<<n;++i)
f[i]=-1+mo;
(f[0]+=1<<n)%=mo;
fwt(f);
(p[0]=p[0]-1+mo)%=mo;
fwt(p);
sum=0;
for (int i=1;i<1<<n;++i){
e[i]=(ll)f[i]*qpow(p[i])%mo;
sum+=e[i];
}
e[0]=(mo-sum%mo)%mo;
fwt(e);
ll inv=qpow(1<<n);
for (int i=0;i<1<<n;++i)
e[i]=e[i]*inv%mo;
for (int i=0;i<1<<n;++i)
printf("%d
",e[i]);
return 0;
}