小W 写了一个二进制式，其中包含个 \(n\) 变量和 \(n-1\) 个符号，每个变量的值只能取 \(0\) 或 \(1\) ，每个符号已经确定，是 and,or,xor 中的一个，但是变量的取值却是没有被固定的。
对于一个变量 $l \(，\)f(l)$ 定义表示：当除 \(l\) 外其他变量的取值固定时，\(l\) 取 \(0\) 和取 \(1\) 两种状态下，表达式的值不相等的概率。
例如对于式子 \(x\ or\ y\)，有 \(f(x)=\frac{1}{2}\)，因为当 \(y=0\) 时，\(x\) 的两种取值会导致表达式的值不相等；但 \(y=1\) 当时，\(x\) 的两种取值无法影响到整个表达式的值（表达式的值始终为 \(1\) ），所以 \(x\) 取 \(0\) 和取 \(1\) 两种状态导致表达式的值不相等的概率为 \(\frac{1}{2}\) 。
再例如对于式子\(x\ xor\ y\)，有 \(f(x)=1\) ，因为无论 \(x\) 的取值如何，\(x\) 的取值不同时，\(x\ xor\ y\) 的值总是不同的。
小 W 想要你求出给定的二进制式中所有 \(f(l)\) 的值，结果对 \(998244353\) 取模 .
在本题中，一个表达式 \(Expr\) 的定义是：
- \(Expr\) 可以是一个单独的变量；
- 否则，\(Expr\) 将表示成 \((Expr1\ op\ Expr2)\) ，其中 \(Expr1\) 和 \(Expr2\) 分别是表达式，\(op\) 是一种运算符，输入保证不会省略任何括号（包括整个表达式外的括号）。
link: 题目描述
首先，根据正则表达式，可以建出一棵二叉树，
用 \(f(x,0/1)\) 表示子树 \(x\) 的值为 \(0/1\) 的方案数 . 这个是可以 \(O(n)\) 求得的 .
接着，考虑 \(g(x)\) 表示子树 \(x\) 内的数可 \(0\) 可 \(1\) 时子树外有多少种方案使得答案可 \(0\) 可 \(1\) .
设 \(x\) 的左儿子为 \(a\) ，右儿子为 \(b\) ，转移方程为 :
如果操作为 \(and\) ，
\(g(a)=\sum g(x)dp(b,i)\)，\(i\) 满足 \(i\&1\not=i\&0\).
如果操作为 \(or\) ，
\(g(a)=\sum g(x)dp(b,i)\) ，\(i\) 满足 \(i|1\not=i|1\) .
如果操作为 \(xor\)，
\(g(a)=\sum g(x)dp(b,i)\)， \(i\) 满足 \(i\ xor\ 1\not=i\ xor\ 0\) .
对 \(b\) 同理 .
那么，对于每个叶子节点的 \(g(x)\) 就是当 \(x\) 取 \(0\) 和 \(x\) 取 \(1\) 时不相同的方案数 .
如果想要改成概率，再乘上 \(2^{n-1}\) 的逆元就可以了 .
时间复杂度 : \(O(n)\)
空间复杂度 : \(O(n)\)
code
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n;
string s;
stack<int>st;
int cnt=0;
char c[500010];
bool leaf[500010];
int L[500010],R[500010]; // À¨ºÅ
int son[500010][2];
int num[500010],id[500010];
int build(int l,int r){
if(R[l]==r)return build(l+1,r-1);
if(l==r){
leaf[cnt]=true;
id[cnt]=num[l];
return cnt++;
}
if(r-l+1==3){
int a=build(l,l),b=build(r,r);
son[cnt][0]=a;son[cnt][1]=b;
c[cnt]=s[l+1];
return cnt++;
}
int pos=-1;
for(int i=l;i<=r;i++){
if(s[i]=='('){
pos=i;
break;
}
}
if(pos==l){
int a=build(pos+1,R[pos]-1),b=build(R[pos]+2,r);
son[cnt][0]=a;son[cnt][1]=b;
c[cnt]=s[R[pos]+1];
return cnt++;
}
if(R[pos]==r){
int a=build(l,pos-2),b=build(pos+1,R[pos]-1);
son[cnt][0]=a;son[cnt][1]=b;
c[cnt]=s[pos-1];
return cnt++;
}
}
inline void upd(int &x,int y){x=(x+y)%mod;}
int dp[500010][2];
void dfs(int x){
if(leaf[x]){
dp[x][0]=dp[x][1]=1;
return;
}
int a=son[x][0],b=son[x][1];
dfs(a);
dfs(b);
for(int i=0;i<2;i++)for(int j=0;j<2;j++){
if(c[x]=='|')upd(dp[x][i|j],1ll*dp[a][i]*dp[b][j]%mod);
if(c[x]=='&')upd(dp[x][i&j],1ll*dp[a][i]*dp[b][j]%mod);
if(c[x]=='^')upd(dp[x][i^j],1ll*dp[a][i]*dp[b][j]%mod);
}
}
int ans[500010];
int f[500010];
void dfs2(int x){
if(leaf[x]){
ans[id[x]]=f[x];
return;
}
int a=son[x][0],b=son[x][1];
for(int i=0;i<2;i++){
if(c[x]=='|'){
if((i|0)!=(i|1)){
upd(f[a],1ll*f[x]*dp[b][i]%mod);
upd(f[b],1ll*f[x]*dp[a][i]%mod);
}
}
if(c[x]=='&'){
if((i&0)!=(i&1)){
upd(f[a],1ll*f[x]*dp[b][i]%mod);
upd(f[b],1ll*f[x]*dp[a][i]%mod);
}
}
if(c[x]=='^'){
if((i^0)!=(i^1)){
upd(f[a],1ll*f[x]*dp[b][i]%mod);
upd(f[b],1ll*f[x]*dp[a][i]%mod);
}
}
}
dfs2(a);
dfs2(b);
}
inline int ksm(int x,int k){
if(k==0)return 1;
int res=ksm(x,k/2);
res=1ll*res*res%mod;
if(k&1)res=1ll*res*x%mod;
return res;
}
int main(){
freopen("binary.in","r",stdin);
freopen("binary.out","w",stdout);
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>s;
if(n==1){
cout<<"1\n";
return 0;
}
for(int i=0;i<(int)s.size();i++)if(s[i]=='x')num[i]=cnt++;
cnt=0;
memset(L,-1,sizeof(L));
memset(R,-1,sizeof(R));
for(int i=0;i<(int)s.size();i++){
if(s[i]=='(')st.push(i);
else if(s[i]==')'){
R[st.top()]=i;
L[i]=st.top();
st.pop();
}
}
memset(son,-1,sizeof(son));
int r=build(0,(int)s.size()-1);
dfs(r);
f[r]=1;
dfs2(r);
int tot=ksm(2,n-1);
for(int i=0;i<n;i++){
int res=1ll*ans[i]*ksm(tot,mod-2)%mod;
cout<<res<<"\n";
}
return 0;
}
/*inline? ll or int? size? min max?*/
/*
4
((x^x)|(x&x))
*/
/*
2
(x|x)
*/
/*
2
(x^x)
*/