#P16500. [NEERC2003 Northern]Artinals阿廷集合

[NEERC2003 Northern]Artinals阿廷集合

题目描述

Nick 最近学习了一类特殊的集合,称为 Artinian 集合,简称 Artinal。这类集合可以用有限形式表示,因此能够由计算机处理。不过,它们的形式化定义略显复杂。

  • 高度不超过 00 的 Artinal 只有空集 ∅\varnothing。
  • 高度不超过 nn 的 Artinal,恰好是由若干个高度不超过 n−1n-1 的 Artinal 组成的有限集合,其中 n≥1n\ge 1。
  • 如果某个集合 AA 对至少一个整数 nn 而言是高度不超过 nn 的 Artinal,那么 AA 就是一个 Artinal。
  • 所有 Artinal 构成的集合记为 U\mathcal U。

显然,高度不超过 nn 的 Artinal 也一定是高度不超过 n+1n+1 的 Artinal。因此,对任意 Artinal AA,可以定义其高度 h(A)h(A):使得 AA 的高度不超过 nn 的最小整数 nn。高度为 nn 的 Artinal 也称为一个 nn-Artinal。

下面定义 U\mathcal U 上的规范序(记为 <<)以及 Artinal 的规范形式。

  • 高度不超过 nn 的 Artinal AA 的规范形式,是如下表示:

    A={A1,A2,…,As},A=\{A_1,A_2,\ldots,A_s\},

    其中每个 AiA_i 都是高度不超过 n−1n-1 的 Artinal,并且

    A1<A2<⋯<As.A_1<A_2<\cdots<A_s.
  • 设

    $$A=\{A_1,A_2,\ldots,A_s\},\qquad B=\{B_1,B_2,\ldots,B_t\}$$

    都以规范形式写出。定义 A<BA<B,当且仅当存在整数 kk,满足

    1≤k≤min⁡(s+1,t),1\le k\le \min(s+1,t),

    且对所有 1≤j<k1\le j<k 都有 Aj=BjA_j=B_j,并且以下两种情况之一成立:

    • k=s+1k=s+1;
    • Ak<BkA_k<B_k。

对任意 Artinal AA,定义其规范表示 repr(A)。它是一个仅由字符 {、} 和 , 组成的字符串:

  • repr(∅) = "{}";

  • 若 A={A1,A2,…,As}A=\{A_1,A_2,\ldots,A_s\} 为规范形式,则

    repr(A) = "{" + repr(A1) + "," + ... + "," + repr(As) + "}"
    

规范表示往往很长,因此还要定义压缩形式。

对任意整数 n≥0n\ge 0,递归定义有限序数 n‾\underline n:

0‾:=∅,\underline 0:=\varnothing, $$\underline{n+1}:=\{\underline n\}\cup \underline n.$$

为了得到一个 Artinal 的压缩规范表示,先写出其规范表示,然后把其中每个有限序数 n‾\underline n 的出现替换为十进制整数 n,但如果该出现包含在某个更大的有限序数 m‾\underline m(m>nm>n)的出现中,则不单独替换它。

下面定义 Artinal 上的运算。运算优先级从高到低如下。

  1. 一元交 ⋂\bigcap:对于非空 Artinal

    A={A1,A2,…,As},A=\{A_1,A_2,\ldots,A_s\},

    定义

    ⋂A:=A1∩A2∩⋯∩As.\bigcap A:=A_1\cap A_2\cap\cdots\cap A_s.
  2. 一元并 ⋃\bigcup:对于任意 Artinal

    A={A1,A2,…,As},A=\{A_1,A_2,\ldots,A_s\},

    定义

    ⋃A:=A1∪A2∪⋯∪As,\bigcup A:=A_1\cup A_2\cup\cdots\cup A_s,

    并规定 ⋃∅:=∅\bigcup\varnothing:=\varnothing。

  3. 二元交:

    A∩B:={x:x∈A∧x∈B}.A\cap B:=\{x:x\in A\land x\in B\}.
  4. 二元并:

    A∪B:={x:x∈A∨x∈B}.A\cup B:=\{x:x\in A\lor x\in B\}.
  5. 差集:

    A−B:={x∈A:x∉B}.A-B:=\{x\in A:x\notin B\}.
  6. 对称差:

    A△B:=(A−B)∪(B−A).A\triangle B:=(A-B)\cup(B-A).

还定义以下关系:

  • 相等 == 与不等 ≠\ne;
  • 包含关系 ⊂\subset 与 ⊃\supset;
  • 元素关系 ∈\in 与 ∋\ni;
  • 规范序关系 <<、>>、≤\le、≥\ge。

Nick 希望你编写一个程序,对 Artinal 进行计算。输入程序由若干条语句组成,每条语句占一行。语句共有五种。

  1. 赋值语句

    <ident> := <expr>
    

    将变量 <ident> 的值设置为表达式 <expr> 的值。

  2. 求值语句

    !<expr>
    

    计算表达式 <expr>,并在单独一行输出其压缩规范表示。

  3. 条件判断语句

    ?<expr><relation><expr>
    

    判断条件是否成立,并在单独一行输出 TRUE 或 FALSE。

  4. 注释语句

    #<任意字符>
    

    将整行原样复制到输出。

  5. 空语句

    仅由空白字符组成的行,不执行任何操作。

使用以下文法:

<ident>    ::= <alpha>{<alpha>}
<alpha>    ::= <letter> | <digit> | "_"
<digit>    ::= "0" | "1" | ... | "9"
<letter>   ::= "A" | "B" | ... | "Z" | "a" | "b" | ... | "z"
<expr>     ::= "{" [<expr>{","<expr>}] "}"
             | <ident>
             | <expr><binop><expr>
             | <unop><expr>
             | "("<expr>")"
<binop>    ::= "+" | "*" | "-" | "^"
<unop>     ::= "+" | "*"
<relation> ::= "<" | ">" | "=" | "<=" | ">=" | "<>"
             | "->" | "<-" | "<<" | ">>"

二元运算符依次对应:

输入符号 含义
+ 并集 ∪\cup
* 交集 ∩\cap
- 差集 −-
^ 对称差 △\triangle

一元运算符含义如下:

输入符号 含义
+ 一元并 ⋃\bigcup
* 一元交 ⋂\bigcap

关系运算符依次对应:

输入符号 含义
< <<
> >>
= ==
<= ≤\le
>= ≥\ge
<> ≠\ne
-> ∈\in
<- ∋\ni
<< ⊂\subset
>> ⊃\supset

圆括号可以像通常一样改变运算优先级。

除组成同一个标识符的连续 <alpha> 字符外,输入中的任意记号之间都可以插入任意数量的空格或制表符。

程序开始执行前:

  • 对于每个满足 0≤n≤290\le n\le 2^9 的整数 nn,名称为其无前导零十进制表示的变量,预先被赋值为有限序数 n‾\underline n;
  • 其他所有变量初始值均为 ∅\varnothing;
  • 标识符区分大小写。

输入格式

输入不超过 100100 行,每行包含一条语句。

每行长度不超过 254254 个字符。

输出格式

对于每条 ?、! 和 # 语句,按照题目描述输出一行。

保证程序执行过程中不会发生运行时错误,例如不会对空集执行一元交运算。

样例输入

!2    + 2
!2*2
!3-4
#  More examples!

00 := 5+3
! 3-5
! 00
! (5-3)*(5+3)
? 3>9
A := {2,3,9}
B := {1,7}
! A^ B
! +239
? 2->00
? 2<<00
? A>>B
! {{{},{{}},{}},B,{A},{B},{A,B}}+B

样例输出

2
2
0
#  More examples!
0
5
{3,4}
FALSE
{1,2,3,7,9}
238
TRUE
TRUE
FALSE
{1,2,7,{1,7},{{1,7}},{{1,7},{2,3,9}},{{2,3,9}}}

数据范围与限制

  • 时间限制:5 s5\text{ s}
  • 空间限制:64 MB64\text{ MB}