CFR 165 C. Another Problem on Strings ( DP )

Problem - 165C - Codeforces
題意：
給一個數字 K 和一個二進位數，求其有多少子字串有恰好 K 個位元是 1。
解法：
預處理前綴和，和各個前綴和出現幾次。
pS[ i ] : 前 i 個位元的前綴和
f2c[ i ] : 某個前綴和出現幾次
此時若 K == 0，答案便是 SIGMA{ ( f2c[ i ] + 1 ) * f2c[ i ] / 2 | 0 ≤ i ≤ | S | }
否則答案是 SIGMA{ f2c[ i ] * f2c[ i + K ] | K ≤ i ≤ | S | }

int K;
string seq;

void init(){
	cin >> K;
	cin >> seq;
}

vi pS;
vi f2p;
vi f2c;

void preprocess(){
	pS = vi( seq.size() + 1 );
	f2p = vi( 1, 0 );
	for( int i = 0; i < seq.size(); ++i )
		pS[ i + 1 ] = pS[ i ] + ( seq[ i ] == '1' );
	for( int i = 1; i <= seq.size(); ++i )
		if( pS[ i ] > pS[ i - 1 ] )
			f2p.push_back( pS[ i ] );
	f2c = vi( seq.size() + 1 );
	for( int i = 0; i <= seq.size(); ++i )
		++f2c[ pS[ i ] ];
}

void solve(){
	ll ans = 0;

	if( K == 0 ){
		for( int i = 0; i < f2c.size(); ++i )
			ans += 1LL * f2c[ i ] * ( f2c[ i ] - 1 ) / 2;
		cout << ans << endl;
		return;
	}

	for( int i = K; i <= seq.size(); ++i )
		ans += 1LL * f2c[ i - K ] * f2c[ i ];
	cout << ans << endl;
}