站外题求助 题目描述

给定一个中缀逻辑表达式，可能有 and，or，xor 三种运算符。

现在，表达式中的一些数字和运算符被抹去了。你需要求出有多少种可能的表达式，满足表达式的值是 1，且可以由给定的表达式填成。

本题中，我们这么定义一个合法的表达式：

单独的数字是合法的表达式。

当 A,C 是一个合法的表达式，B 是一种运算符，(ABC) 也是一个合法的表达式。

输入格式

一行一个字符串，表示给定的表达式。

在本题中，我们用 & 代表 and，| 代表 or，^ 代表 xor，# 代表被抹去的运算符，？ 代表被抹去的数字。

输出格式

一行一个自然数，表示可能的表达式数量。

由于可能的答案过多，你只需要输出对 998244353 取模的结果。

样例输入 1

(1#?) 样例输出 1

4 样例输入 2

(?#((0#?)|?)) 样例输出 2

40 样例输入 3

((1#?)#1) 样例输出 3

12 提示/说明

记 n 为表达式中运算符的数量。

对于 30% 的数据，n≤10

对于 60% 的数据，n≤1000

对于 100% 的数据，n≤1e5

还有一题 题目描述

王老师一直都很喜欢猫，这天他终于下定决心——要养猫！

王老师养的猫越多，他自然就会越开心，但是他到了猫屋以后，老板告诉他，猫和人一样，也不喜欢很很多同类一起生活在同一个房间里，这就是属于猫咪的快乐度！

而现在猫屋里总共有 n 只小猫，每只小猫都有自己原本的快乐度。

也就是如果王老师只养第 i 只小猫的话，那这只小猫的快乐度就是 a i ​

而如果王老师每多养一只小猫，第 i 只小猫的快乐度就会下降 b i ​ 点 王老师虽然喜欢猫，也希望养很多猫，但是他终究希望自己家的猫咪可以快乐。

所以现在他想要一种养猫的方案，使得自己带回家的所有小猫的快乐度总和最高，当然如果有快乐度总和相同的方案，王老师自然希望猫越多越好！ 样例输入 1

6 10 10 10 10 10 9 2 2 2 2 2 3 样例输出 1

18 3