#P8997. [CEOI2022] Homework

[CEOI2022] Homework

题目描述

这是 Helena 的数学作业中的一道题:

我们定义合法表达式如下:

  • ? 是合法表达式,这表示一个未知数。
  • 如果 A,BA,B 均为合法表达式,那么 min(AA,BB)max(AA,BB) 均为合法表达式,这分别表示取左右两边的最大值/最小值。

? 的个数为 NN,现在给出一个合法表达式,将每一个问号替换为 1N1\sim N 中的任意一个数并且每一个数不能使用多次,可以得到多少种不同的答案?

可怜的 Helena 并不会做,请你帮帮她。

输入格式

仅一行一个字符串表示给出的合法表达式。

输出格式

输出一个整数,表示不同答案的个数。

min(min(?,?),min(?,?))
1
max(?,max(?,min(?,?)))
2
min(max(?,?),min(?,max(?,?)))
3

提示

样例 1 解释

无论权值如何选择,最后的答案都会是 min{1,2,3,4}\min\{1,2,3,4\},也就是 11

样例 2 解释

答案为 44 的方案是: 4=max(4,max(3,min(2,1))),答案为 33 的方案是 3=max(3,max(2,min(1,4))),可以证明答案不可能为 1122

数据规模与约定

对于全部数据,2N1062\le N\le 10^6

Subtask 编号 特殊限制 得分
11 N9N\le 9 1010
22 N16N\le 16 1313
33 对于任意 min(AA,BB)max(AA,BB)AABB 中有一个为 ?
44 N103N\le 10^3 3030
55 无特殊限制 3434