[codechef] REBIT：准备好每一位（表达式/DP）

Problem

题目地址

Solution

前置知识

• 中缀转后缀

• 中缀表达式求值（栈）

中缀表示式序列可以转化成一棵二叉树。发现计算概率可以转化成计数，在二叉树上做一个树形DP就好了。

Code

Talk is cheap.Show me the code.

#include
using namespace std;
typedef int LL;
#define int long long
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
    return x * f;
}
const int N = 1e6+7, mod = 998244353;
int len,tot;
int ls[N],rs[N];
int f[N][4];
char str[N],c[N];
struct Node {
    int x,y;
    Node operator & (const Node &el) const {
        return (Node)<%x&el.x, y&el.y%>;
    }
    Node operator | (const Node &el) const {
        return (Node)<%x|el.x, y|el.y%>;
    }
    Node operator ^ (const Node &el) const {
        return (Node)<%x^el.x, y^el.y%>;
    }
    bool operator < (const Node &el) const {
        return (x==el.x ? y inode;
map acinode;
void Init() {
    inode[0] = (Node)<%0,0%>, inode[1] = (Node)<%1,1%>, inode[2] = (Node)<%0,1%>, inode[3] = (Node)<%1,0%>;
    acinode[(Node)<%0,0%>] = 0, acinode[(Node)<%1,1%>] = 1, acinode[(Node)<%0,1%>] = 2, acinode[(Node)<%1,0%>] = 3;
}
inline void Add(int &x,int y) {
    x = (x+y>mod ? x+y-mod : x+y);
}
void Dfs(int u) {
    int x = ls[u], y = rs[u];
    if(x) {
        Dfs(x); Dfs(y);
    } else return ;
    for(int i=0;i<4;++i) {
        Node ii = inode[i];
        for(int j=0;j<4;++j) {
            Node jj = inode[j];
            if(c[u] == '&') {
                Add(f[u][acinode[ii & jj]], f[x][i]*f[y][j]%mod);
            } else if(c[u] == '|') {
                Add(f[u][acinode[ii | jj]], f[x][i]*f[y][j]%mod);
            } else if(c[u] == '^') {
                Add(f[u][acinode[ii ^ jj]], f[x][i]*f[y][j]%mod);
            }
        }
    }
}
int Pow(int x,int y) {
    int res = 1, base = x;
    while(y) {
        if(y&1) res = res*base%mod; base = base*base%mod; y >>= 1;
    }
    return res;
}
void work() {
    for(int i=1;i<=tot;++i) {
        c[i] = ls[i] = rs[i] = 0;
        for(int j=0;j<4;++j) f[i][j] = 0;
    }
    tot = 0;
    scanf("%s",str+1); len = strlen(str+1)
    stack sta; stack num;
    for(int i=0;i<=len+1;++i) {
        if(str[i] == '(') {
            sta.push(str[i]);
        } else if(str[i] == ')') {
            while(sta.top() != '(') {
                char opt = sta.top(); sta.pop();
                int x = num.top(); num.pop();
                int y = num.top(); num.pop();
                c[++tot] = opt; ls[tot] = y, rs[tot] = x;
                num.push(tot);
            }
            sta.pop();
        } else if(str[i] == '#') {
            c[++tot] = str[i]; num.push(tot);
        } else {
            sta.push(str[i]);
        }
    }
    for(int i=1;i<=tot;++i) {
        if(!ls[i]) {
            for(int j=0;j<4;++j) f[i][j] = 1;
        }
    }
    Dfs(tot);
    int sum = 0;
    for(int i=0;i<4;++i) Add(sum, f[tot][i]);
    int inv = Pow(sum,mod-2);
    for(int i=0;i<4;++i) printf("%lld ",f[tot][i]*inv%mod);
    puts("");
}
signed main()
{
    Init();
    int T = read();
    while(T--) work();
    return 0;
}
/*
2
#
(#&#)
()

748683265 748683265 748683265 748683265
436731905 935854081 811073537 811073537
*/

Summary

• 中缀表示式序列可以转化成一棵二叉树。从而将此类问题转化为树上问题。