問題
背景
正在进行公式检索研究的比格布里奇伯爵有一天想到,通过计算公式的哈希值,或许可以更高效地进行公式检索。
因此,对于满足某些特定条件的多项式,他决定对于变量 1 或 -1 进行赋值,并在计算该多项式时,将使该多项式取得最小值的变量赋值总数作为该多项式的哈希。
但是,比格布里奇伯爵还忙于实现其他各种想法。
因此,你需要代替比格布里奇伯爵编写一个计算公式哈希值的程序。
課題
30 变量和以下的 2 次多項式 P 在以下约束条件下给出。
- 多项式中出现的变量是
A-Z,a-d任何一个 - 多项式必须是 Σ 1 * x_i * x_j 这种形式
- x_i, x_j 是
您也可以写
A-Z,a-d中的某一种 - a * A + A * a => 2 * a * A 或、 A * A + A * A => 2 * A * A 当整理后,如果有系数不是 1 的项,将不予提供。
- x_i, x_j 是
您也可以写
- 所有变量在多项式中最多只出现 4 次。
当各变量的取值只为 -1, 1 之一时,求多项式取得最小值的变量分配总数。
配点
300
入力
输入按以下格式给出。
P
制約
入力 P 是
您也可以写 1 字母变量(A-Z和
按字典顺序比较a-d之一)表示乘法。 *表示加法。+组成。
P 中
您可以确定是否有A-Z,a-d,*,+之外的字符不会出现。
满足课题中所写条件。
部分点
针对此问题设置了部分分数。这个问题的测试用例 30 这些点还满足以下约束。
- 输入中出现的变量种类为 20 種類以下
出力
。取得最小值的变量分配总数 T 该值应乘以 1 行。
入力例1
a*A
出力例1
2
a=1 , A=-1 或 通过替换为 a=-1 , A=1 这就是所谓的 2 种分配会取得最小值。
入力例2
a*A+b*b+c*a+b*a+A*b
出力例2
6
入力例3
A*C+A*V+A*W+B*M+B*R+B*c+C*J+C*T+D*M+D*Q+D*b+E*P+E*Y+E*c+F*Q+F*R+F*d+G*H+G*X+G*Y+H*J+H*L+I*K+I*L+I*M+J*Q+K*L+K*Z+N*T+N*Y+N*d+O*S+O*X+O*Z+P*U+P*V+R*U+S*V+S*b+T*d+U*a+W*X+W*b+Z*a+a*c
出力例3
30