Cerința

Să se scrie funcția cu următorul antet:

long long SecvBiti(char s[])

Funcția primește ca parametru un șir de caractere din mulțimea {'0', '1'} și returnează numărul secvențelor cu proprietatea că numărul biților de 1 din secvență este egal cu numărul biților de 0.

Restricții și precizări

• 2 ≤ lungimea șirului ≤ 1.000.000

Exemplu

SecvBiti("1001") = 3

Explicație

Secvențele sunt: 1001, 10, 01.

Important

Soluţia propusă va conţine definiţia funcţiei cerute. Prezenţa în soluţie a altor instrucţiuni poate duce erori de compilare sau de execuţie care vor avea ca efect depunctarea soluţiei. De asemenea, e posibil ca folosirea funcțiilor predefinite pentru șiruri de caractere să dea erori de compilare

#include <bits/stdc++.h>
int f[2000001];
long long SecvBiti(char s[])
{
    int l = strlen(s);
    f[l]=1;
    long long int cnt = 0;
    for(int i = 0 ; i < l ; ++i)
        if(s[i]=='1') cnt++ , f[l+cnt]++;
        else cnt-- , f[l+cnt]++;
    cnt=0;
    for(int i = 0 ; i < 2*l ; ++i)
        cnt = cnt + f[i] * (f[i]-1LL) / 2;
    return cnt;
}