AOJ 2348 Testing Circuits

問題

論理変数、|, &, ~, および括弧からなるbooleanの式が与えられる。
ただし、一つの変数は、式中にただ一度しか現れない。

この式をtrueにする変数の真偽値の割り当ては何通りあるか、mod 10^9 + 7で求めよ。
式の正確な定義は問題文のBNF記法を参照。

制約条件

式の長さは1000000以下

方針

一つの変数が1度しか登場しないという制約があるので、
exp1 | exp2を真にする割り当て方は、exp1, exp2全体の割り当て方から、両方を偽にする割り当て方の場合の数を引いたもの、
偽にする割り当て方は、両方を偽にする場合の数の積、という風に計算できる。

exp1 & exp2を真にする割り当て方も同様に計算できる。
なので、構文解析して式を真にする割り当ての数、偽にする割り当ての数を計算していけばいい。

普通に再帰で書くとスタックオーバーフローして死ぬので、
再帰をスタックを使ってループで書いた。
こういう本質じゃない制限は本当にただの嫌がらせでしかないからやめてほしい。

ソースコード

const int mod = (int)1e9 + 7;
char in[1000001];
int pos;

#define RETURN \
	RES.pb(res); \
	if(RET.back() == 1) goto EXPR1; \
	if(RET.back() == 2) goto EXPR2; \
	if(RET.back() == 11) goto TERM1; \
	if(RET.back() == 12) goto TERM2; \
	if(RET.back() == 21) goto FACTOR1; \
	if(RET.back() == 22) goto FACTOR2;

pi expr(){
	vi RET;
	vector<pi> RES;
	vector<bool> NEG;
	pi res, tmp; bool neg;
	ll f, t;
	
	EXPR:
	RET.pb(1);
	goto TERM;
	EXPR1:
	res = RES.back(); RES.pop_back(); RET.pop_back();
	while(in[pos] == '|'){
		pos++;
		RET.pb(2);
		RES.pb(res);
		goto EXPR;
		EXPR2:
		tmp = RES.back(); RES.pop_back(); RET.pop_back();
		res = RES.back(); RES.pop_back();
		f = (ll)res.S * tmp.S;
		t = ll(res.F + res.S) * (tmp.F + tmp.S) - f % mod + mod;
		res = mp(t % mod, f % mod);
	}
	if(RET.empty()) return res;
	RETURN
	
	TERM:
	RET.pb(11);
	goto FACTOR;
	TERM1:
	res = RES.back(); RES.pop_back(); RET.pop_back();
	while(in[pos] == '&'){
		pos++;
		RES.pb(res);
		RET.pb(12);
		goto FACTOR;
		TERM2:
		tmp = RES.back(); RES.pop_back(); RET.pop_back();
		res = RES.back(); RES.pop_back();
		t = (ll)res.F * tmp.F;
		f = ll(res.F + res.S) * (tmp.F + tmp.S) - t % mod + mod;
		res = mp(t % mod, f % mod);
	}
	RETURN
	
	FACTOR:
	neg = 0;
	while(in[pos] == '~') neg ^= 1, pos++;
	if(in[pos] == 'x'){
		RET.pb(21);
		NEG.pb(neg);
		goto VAR;
		FACTOR1:
		neg = NEG.back(); NEG.pop_back(); RET.pop_back();
		res = RES.back(); RES.pop_back();
		RETURN
	}
	assert(in[pos] == '(');
	pos++;
	RET.pb(22);
	NEG.pb(neg);
	goto EXPR;
	FACTOR2:
	res = RES.back(); RES.pop_back(); RET.pop_back();
	neg = NEG.back(); NEG.pop_back();
	if(neg) swap(res.first, res.second);
	pos++;
	RETURN
	
	VAR:
	assert(in[pos] == 'x');
	pos++;
	while(isdigit(in[pos])) pos++;
	res = mp(1, 1);
	RETURN
}

int main(){
	gets(in);
	cout << expr().first << endl;
	return 0;
}