【6.28校内test】T3 【音乐会】道路千万条

首先，你可以忽略上面的一大坨题面，只需要看说明的那一小部分就好啦。

然后理解题意：

就是说我们要给这n-1个运算符指定一个顺序，统计所有值为true的方案数pt，统计所有值为false的方案数pf，然后算pt/(pt+pf) mod 998244353。

然后water_lift就想到了表达式的值【题解】，考虑最后算哪个运算符，一共有n-1种选择。

然后三种情况：

1.最后计算的运算符是‘&’。

那么使表达式为true的方案数就是运算符左边为true的方案数*运算符右边为true的方案数（乘法原理）。

使表达式为false的方案数是左边为true*右边为false+左边false*右边true+左边false*右边false。

2.最后计算的运算符是‘|’。

那么使表达式为true的方案数为：左边true*右边false+左边false*右边true+左边true*右边true；

使表达式为false的方案数为：左边false*右边false；

3.最后计算的运算符是'^'。

那么使表达式为true的方案数为：左边false*右边true+左边true*右边false；

使表达式为false的方案数为：左边false*右边false+左边true*右边true；

所以定义两个数组，t[l][r]表示区间[l,r]为true的方案数，f[l][r]表示区间[l,r]为false的方案数。

那么最终答案就是t[1][n]/(t[1][n]+f[1][n]）mod 998244353；

然后显然是可以搜索的，但是我写锅了（并且我不想看）

因此我们还是看DP的解法吧；

就是类比表达式的值，然后求就好辣；（主要是不知道该写啥qwq）

#include<bits/stdc++.h>

using namespace std;

inline int read(){

    int ans=;

    char last=' ',ch=getchar();

    while(ch>''||ch<'') last=ch,ch=getchar();

    while(ch<=''&&ch>='') ans=(ans<<)+(ans<<)+ch-'',ch=getchar();

    if(last=='-') ans=-ans;

    return ans;

}

inline char gc(){

    char c;

    do{

        c=getchar();

    }while(c==' '||c=='\n'||c=='\r'||c=='\0'||c=='\t');

    return c;

}

int n;

char s[],ops[];

long long t[][],f[][];

const int mod=;

pair<long long,long long>extgcd(long long a,long long b){

    if(b==){

        return make_pair<long long ,long long>(,);

    }

    pair<long long,long long>rtn=extgcd(b,a%b);

    rtn.first^=rtn.second^=rtn.first^=rtn.second;//交换两个变量

    rtn.second-=a/b*rtn.first;

    return rtn;

}

int main(){

    n=read();

    for(int i=;i<=n-;i++){

        s[i]=gc();

        ops[i]=gc();

    }

    s[n]=gc();

    for(int i=;i<=n;i++){

        if(s[i]=='t')

          t[i][i]=,f[i][i]=;

        else

          t[i][i]=,f[i][i]=;

    }

    for(int len=;len<=n;len++){

        for(int i=;i+len-<=n;i++){

            int j=i+len-;

            for(int k=i;k<j;k++){

                if(ops[k]=='&'){

                t[i][j]=(t[i][j]+(t[i][k]*t[k+][j])%mod)%mod;

                f[i][j]=(f[i][j]+(t[i][k]*f[k+][j])%mod+(f[i][k]*t[k+][j])%mod+(f[i][k]*f[k+][j])%mod)%mod;

                }

                if(ops[k]=='|'){

                    f[i][j]=(f[i][j]+(f[i][k]*f[k+][j])%mod)%mod;

                    t[i][j]=(t[i][j]+(t[i][k]*f[k+][j])%mod+(f[i][k]*t[k+][j])%mod+(t[i][k]*t[k+][j])%mod)%mod;

                }

                if(ops[k]=='^'){

                    t[i][j]=(t[i][j]+(t[i][k]*f[k+][j])%mod+(f[i][k]*t[k+][j])%mod)%mod;

                    f[i][j]=(f[i][j]+(f[i][k]*f[k+][j])%mod+(t[i][k]*t[k+][j])%mod)%mod;

                }

            }

        }

    }

    cout<<(t[][n]*((extgcd(t[][n] +f[][n]%mod,mod).first%mod+mod)%mod))%mod<<endl;

    return ;

}

end-

巴特西

【6.28校内test】T3 【音乐会】道路千万条

最新文章

热门文章