$\bold{1.\;Statements}$

依照数据以及 $\mathsf{SPJ}$，认为题面实际上是允许 !(a&b) 类似的逻辑表达式存在的，而非只有 元素 才能使用 [!]（否则会有若干组数据无解。）

还有一些零碎的问题，此为修改后的题面：

[CTSC2000] 逻辑范式

题目描述

逻辑学是对命题以及命题真假性进行研究的一门科学。命题一般用一个小写字母表示，任何命题的值非真即假。我们用 T 表示命题的值为真，用 F 表示命题的值为假。

命题间的运算符称为命题操作联结词，简称联结词。逻辑系统中最基本的三个联结词是非、且和或，为了简便，我们用 $!$ 表示联结词非，用 $\&$ 表示联结词且，用 $|$ 表示联结词或。

联结词非是一个一元联结词，对于任意命题 $p$ ，$!p$ 的真值总是和 $p$ 相反。

联结词且又称合取，是一个二元联结词，对于任意命题 $p$ 和 $q$ ，当且仅当 $p$ 和 $q$ 同为真时， $p\&q$ 为真，否则 $p\&q$ 为假。

联结词或又称析取，是一个二元联结词，对于任意命题 $p$ 和 $q$ ，当且仅当 $p$ 和 $q$ 同为假时， $p|q$ 为假，否则 $p|q$ 为真。

下面给出三个基本命题运算联结词的真值表：

命题 $p$	命题 $q$	$!p$	$p\&q$	$p$|$q$
T	T	F	T	T
T	F	F	F	T
F	T	T	F	T
F	F	T	F	F

逻辑表达式是由命题、联结词和括号组成的。它的定义如下：

<表达式> ::= <合取式> or <析取式> or (<表达式>) or <元素> or !<表达式>

<合取式> ::= <表达式>&<表达式>

<析取式> ::= <表达式>|<表达式>

<元素> ::= [!]<命题>

注：其中 <命题> 是 $a$ 到 $z$ 的小写字母，::= 表示定义为， or 表示或， [] 内的项可以出现一次或不出现，例如，以下式子均构成了一个合法表达式：!(a&!d)|!(b&c)，a&b|c&!(d|!d)。

对表达式的求值过程是根据表达式中各命题的值和真值表进行命题运算操作的过程。运算优先级为 $()$ 、 $!$ 、 $\&$ 和 $|$ 。$\&$ 和 $|$ 的优先级相同。相同优先级从左到右运算。

与或非逻辑范式（这里简称为范式）是一种逻辑表达式，它能够符合特定的真值表。例如一般逻辑里定义的蕴涵运算 $\rightarrow$ 的真值表为：

命题 $p$	命题 $q$	$p \rightarrow q$
T	T	T
T	F	F
F	T	T
F	F	T

我们可以用表达式 $!p|q$ 来表示这个蕴涵运算。表达式 $!p|q$ 的真值表为：

命题 $p$	命题 $q$	$!p$|$q$
T	T	T
T	F	F
F	T	T
F	F	T

这样，我们就说 $p→q$ 的范式为 $!p|q$ 。

完备定理告诉我们，对于任意一个 $n$ 元逻辑运算函数 $A$ ，已知 $A$ 的真值表，总可以求出 $A$ 的范式。范式只含命题、三个基本联结词和括号。例如，下面是一个三元运算 $A(p,q,r)$ 的真值表：

命题 $p$	命题 $q$	命题 $r$	$A(p,q,r)$
T	T	T	T
T	T	F	T
T	F	T	T
T	F	F	F
F	T	T	T
F	T	F	F
F	F	T	F
F	F	F	F

也就是说，在命题 $p,q,r$ 有两个或两个以上为真时， $A$ 为真；反之 $A$ 为假。

当然，范式并不是唯一的。假设存在一种 $A$ 的范式为 $(p\&q\&r)|(!p\&q\&r)|(p\&!q\&r)|(p\&q\&!r)$ ， 表达式 $(p\&q)|(q\&r)|(p\&r)$ 也是 $A$ 的范式，并且它的长度比前式更短。

我们的要求是：给定 $n$ 元函数 $A$ 的真值表，求 $A$ 的范式，并要求范式尽可能短。

输入格式

输入文件第一行为 $n$ ，表示 $A$ 是 $n$ 元函数。随后有 $2^n$ 行，每行为一个长度为 $n+1$ 的字符串。字符串仅包含字符 T 和 F 。前 $n$ 个依次表示第 $n$ 个命题的值，最后一个表示当 $n$ 个命题按此取值时 $A$ 的值。

输出格式

输出文件包含一行，为你给出的范式。命题依次用小写字母 $a,b,c,d,\cdots$ 表示。

样例 #1

样例输入 #1

3
TTTT
TTFT
TFTT
TFFF
FTTT
FTFF
FFTF
FFFF

样例输出 #1

a&b|(a|b&c)

提示

$n \leq 6$。

评分标准：

如果你给定的范式错误或者在规定时间内没有出解，该测试点得 $0$ 分。

如果你给定的范式长度小于等于标准答案的长度，该测试点得满分。

如果你给定的范式长度大于等于标准答案长度的两倍，该测试点得 $0$ 分。

如果你给定的范式长度大于标准答案的长度，小于标准答案长度的两倍，该测试 点得分计算公式为：

$Score=FullScore \times \frac{2L_{std}-L}{L_{std}}$

其中 $FullScore$ 为该测试点满分， $L_{std}$ 为标准答案长度， $L$ 为你的答案长度。

感谢 tiger2005 提供 $\bold{SPJ}$！

# [CTSC2000] 逻辑范式

## 题目描述

逻辑学是对命题以及命题真假性进行研究的一门科学。命题一般用一个小写字母表示，任何命题的值非真即假。我们用 ```T``` 表示命题的值为真，用 ```F``` 表示命题的值为假。

命题间的运算符称为命题操作联结词，简称联结词。逻辑系统中最基本的三个联结词是非、且和或，为了简便，我们用 $!$ 表示联结词非，用 $\&$ 表示联结词且，用 $|$ 表示联结词或。

联结词非是一个一元联结词，对于任意命题 $p$ ，$!p$ 的真值总是和 $p$ 相反。

联结词且又称合取，是一个二元联结词，对于任意命题 $p$ 和 $q$ ，当且仅当 $p$ 和 $q$ 同为真时， $p\&q$ 为真，否则 $p\&q$ 为假。

联结词或又称析取，是一个二元联结词，对于任意命题 $p$ 和 $q$ ，当且仅当 $p$ 和 $q$ 同为假时， $p|q$ 为假，否则 $p|q$ 为真。

下面给出三个基本命题运算联结词的真值表：

| 命题 $p$ | 命题 $q$ | $!p$ | $p\&q$ | $p$\|$q$   |
| :----------: | :----------: | :----------: | :----------: | :----------: |
| T | T | F | T | T |
| T | F | F | F | T | 
| F | T | T | F | T |
| F | F | T | F | F | 


逻辑表达式是由命题、联结词和括号组成的。它的定义如下：

```<表达式> ::= <合取式> or <析取式> or (<表达式>) or <元素> or !<表达式>```

```<合取式> ::= <表达式>&<表达式>```

```<析取式> ::= <表达式>|<表达式>```

```<元素>   ::= [!]<命题>```

注：其中 <命题> 是 $a$ 到 $z$ 的小写字母，```::=``` 表示定义为， ```or``` 表示或， ```[]``` 内的项可以出现一次或不出现，例如，以下式子均构成了一个合法表达式：`!(a&!d)|!(b&c)`，`a&b|c&!(d|!d)`。

对表达式的求值过程是根据表达式中各命题的值和真值表进行命题运算操作的过程。运算优先级为 $()$ 、 $!$ 、 $\&$ 和 $|$ 。$\&$ 和 $|$ 的优先级相同。相同优先级从左到右运算。

与或非逻辑范式（这里简称为范式）是一种逻辑表达式，它能够符合特定的真值表。例如一般逻辑里定义的蕴涵运算 $\rightarrow$ 的真值表为：

| 命题 $p$ | 命题 $q$ | $p \rightarrow q$ |
| :----------: | :----------: | :----------: |
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |


我们可以用表达式 $!p|q$ 来表示这个蕴涵运算。表达式  $!p|q$ 的真值表为：

| 命题 $p$ | 命题 $q$ | $!p$\|$q$ |
| :----------: | :----------: | :----------: |
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |

这样，我们就说 $p→q$ 的范式为 $!p|q$ 。

完备定理告诉我们，对于任意一个 $n$ 元逻辑运算函数 $A$ ，已知 $A$ 的真值表，总可以求出 $A$ 的范式。范式只含命题、三个基本联结词和括号。例如，下面是一个三元运算 $A(p,q,r)$ 的真值表：

| 命题 $p$ | 命题 $q$ | 命题 $r$ | $A(p,q,r)$ |
| :----------: | :----------: | :----------: | :----------: |
| T | T | T | T |
| T | T | F | T |
| T | F | T | T |
| T | F | F | F |
| F | T | T | T |
| F | T | F | F |
| F | F | T | F |
| F | F | F | F |

也就是说，在命题 $p,q,r$ 有两个或两个以上为真时， $A$ 为真；反之 $A$ 为假。

当然，范式并不是唯一的。假设存在一种 $A$ 的范式为 $(p\&q\&r)|(!p\&q\&r)|(p\&!q\&r)|(p\&q\&!r)$ ， 表达式 $(p\&q)|(q\&r)|(p\&r)$ 也是 $A$ 的范式，并且它的长度比前式更短。

我们的要求是：给定 $n$ 元函数 $A$ 的真值表，求 $A$ 的范式，并要求范式尽可能短。

## 输入格式

输入文件第一行为 $n$ ，表示 $A$ 是 $n$ 元函数。随后有 $2^n$ 行，每行为一个长度为 $n+1$ 的字符串。字符串仅包含字符 ```T``` 和 ```F``` 。前 $n$ 个依次表示第 $n$ 个命题的值，最后一个表示当 $n$ 个命题按此取值时 $A$ 的值。

## 输出格式

输出文件包含一行，为你给出的范式。命题依次用小写字母 $a,b,c,d,\cdots$ 表示。

## 样例 #1

### 样例输入 #1

3 TTTT TTFT TFTT TFFF FTTT FTFF FFTF FFFF

### 样例输出 #1

a&b|(a|b&c)

## 提示

$n \leq 6$。

**评分标准**：

如果你给定的范式错误或者在规定时间内没有出解，该测试点得 $0$ 分。

如果你给定的范式长度小于等于标准答案的长度，该测试点得满分。

如果你给定的范式长度大于等于标准答案长度的两倍，该测试点得 $0$ 分。

如果你给定的范式长度大于标准答案的长度，小于标准答案长度的两倍，该测试
点得分计算公式为： 

$Score=FullScore \times \frac{2L_{std}-L}{L_{std}} $

其中 $FullScore$ 为该测试点满分， $L_{std}$ 为标准答案长度， $L$ 为你的答案长度。

**感谢 [tiger2005](https://www.luogu.com.cn/user/60864) 提供 $\bold{SPJ}$！**

$\bold{2.\;SPJ}$

原作者：@tiger2005

#include "testlib.h"
#include <string>
#include <vector>
using namespace std;
string curr, anss, curr2;
vector<int> v1, v2;
vector<int> sta;
int Memory[6], N;
bool getNum(string, int, int, vector<int>);
bool Exp(string str, int st, int ed, vector<int> mat)
{
    if (str[st] == '(')
    {
        while (mat[st] == ed)
            ++st, --ed;
        return getNum(str, st, ed, mat);
    }
    if (st != ed)
        quitf(_wa, "Wrong answer");
    if (str[st] >= 'a' && str[st] < 'a' + N)
    {
        return Memory[(int)str[st] - 'a'];
    }
    else
        quitf(_wa, "Wrong answer");
}
bool isNot(string str, int st, int ed, vector<int> mat)
{
    if (str[st] != '!') // Was str[0] != '!' Before.
        return Exp(str, st, ed, mat);
    bool num = false;
    while (st <= ed && str[st] == '!')
        ++st, num ^= 1;
    if (st > ed)
        quitf(_wa, "Wrong answer");
    if (num)
        return !Exp(str, st, ed, mat);
    return Exp(str, st, ed, mat);
}
bool getNum(string str, int st, int ed, vector<int> mat)
{
    bool hav = false;
    for (int i = st; i <= ed; i++)
    {
        if (mat[i] != -1)
        {
            i = mat[i];
            continue;
        }
        if (str[i] == '&' || str[i] == '|')
            hav = true;
    }
    if (!hav)
        return isNot(str, st, ed, mat);
    int ret = -1;
    bool lastType;
    for (int i = st; i <= ed; i++)
    {
        if (mat[i] != -1)
        {
            i = mat[i];
            continue;
        }
        if (str[i] == '&' || str[i] == '|')
        {
            if (ret == -1)
                ret = isNot(str, st, i - 1, mat);
            else
            {
                if (lastType)
                    ret = ret & isNot(str, st, i - 1, mat);
                else
                    ret = ret | isNot(str, st, i - 1, mat);
            }
            lastType = (str[i] == '&' ? true : false);
            st = i + 1;
        }
    }
    if (st <= ed)
    {
        if (lastType)
            ret = ret & isNot(str, st, ed, mat);
        else
            ret = ret | isNot(str, st, ed, mat);
    }
    return (bool)ret;
}
int main(int argc, char *argv[])
{
    registerTestlibCmd(argc, argv);
    anss = ans.readLine();
    curr = ouf.readLine();
    for (int i = 0; curr[i]; i++)
        if (curr[i] != ' ' && curr[i] != '\t')
            curr2 += curr[i];
    N = inf.readInt();
    for (int i = 0; curr2[i]; i++)
    {
        v1.push_back(-1);
        if (curr2[i] == ')')
        {
            if (sta.empty())
                quitf(_wa, "Wrong answer");
            v1[sta.back()] = i;
            sta.pop_back();
        }
        if (curr2[i] == '(')
            sta.push_back(i);
    }
    if (!sta.empty())
        quitf(_wa, "Wrong answer");
    for (int i = 0; anss[i]; i++)
    {
        v2.push_back(-1);
        if (anss[i] == ')')
        {
            v2[sta.back()] = i;
            sta.pop_back();
        }
        if (anss[i] == '(')
            sta.push_back(i);
    }
    memset(Memory, -1, sizeof(Memory));
    for (int i = 0; i < (1 << N); i++)
    {
        int x = i;
        for (int i = 0; i < N; i++)
        {
            Memory[i] = x & 1;
            x >>= 1;
        }
        if (getNum(curr2, 0, curr2.length() - 1, v1) != getNum(anss, 0, anss.length() - 1, v2))
            quitf(_wa, "Wrong answer");
    }
    if (curr.length() > anss.length() && curr.length() < 2 * anss.length())
        quitp(1.0 * (2 * anss.length() - curr.length()) / anss.length(), "Answer too long");
    if (curr.length() >= 2 * anss.length())
        quitf(_wa, "Answer really long");
    quitf(_ok, "Answer correct");
}