東京大学プログラミングコンテスト2014

L - セミ時雨ハッシュ


Time limit時間制限 : 3sec / Memory limitメモリ制限 : 256MB

問題

背景

数式検索の研究をしていたビッグブリッジ伯爵はある日、数式のハッシュ値を計算することによって効率よく数式検索をすることが出来るのではないかと考えた。
そこで、ある特定の条件を満たす多項式に対しては、変数に 1-1 を割り当ててその多項式を計算した時にその多項式が最小値を取るような変数の割り当ての総数を、その多項式のハッシュとすることにした。

しかし、ビッグブリッジ伯爵は他にも様々なアイディアを実装するので忙しい。
そこであなたは、ビッグブリッジ伯爵の代わりに数式のハッシュ値を計算するプログラムを書くことになった。

課題

30 変数以下の 2 次多項式 P が以下の制約のもとで与えられる。

各変数の値が -1, 1 のどちらかしかとらないとき、多項式が最小値を取るような変数の割り当て方の総数を求めよ。

配点

300

入力

入力は以下の形式で与えられる。

P

制約

入力 P1 文字の変数(A-Za-dのどれか)と掛け算を表す *、足し算を表す+のみで構成される。
P の中にA-Z,a-d,*,+以外の文字は出現しない。
課題に書かれている条件を満たす。

部分点

この問題には部分点が設定されている。この問題のテストケースのうち 30 点分は追加で以下の制約を満たす。

出力

最小値を取るような変数の割り当て方の総数 T1 行で出力せよ。


入力例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

Submit提出する