CFR 476 B. Dreamoon and WiFi ( Probability )

Problem - B - Codeforces
題意：
給兩個序列，序列中的+表示向右走一個，-表示向左走一格，?表示一半機率向左，一半機率向右。求多少機率兩者終點相同。
解法：
求有多少 ? 以及有多少需要變成+，數學求機率。

string A, B;

void init(){
	cin >> A >> B;
}

int Ax, Bx;

void preprocess(){
	Ax = Bx = 0;
	for( int i = 0; i < A.size(); ++i )
		Ax += A[ i ] == '+' ? 1 : -1;
	for( int i = 0; i < B.size(); ++i )
		Bx += B[ i ] == '+' ? 1 : B[ i ] == '-' ? -1 : 0;
}

double prob( int n, int k ){
	function< int ( int ) > fact = [ & ]( int x ){ return x == 0 ? 1 : fact( x - 1 ) * x; };
	return 1.0 * fact( n ) / fact( n - k ) / fact( k ) * pow( 0.5, n );
}

void solve(){
	int diff = abs( Ax - Bx ); // p - n = diff
	int qcnt = count_if( B.begin(), B.end(), [ & ]( char ch ){ return ( ch == '?' ); } ); // p + n = qcnt
	int head = diff + qcnt >> 1;
	if( head > qcnt )
		cout << 0 << endl;
	else
		cout << fixed << setprecision( 10 ) << prob( qcnt, head ) << endl;
}