Liczba ciągów zero-jedynowych spełniających dodatkowy warunek.

Dana jest liczba parzysta n. Szukam wydajnego sposobu na wyliczenie liczby ciągów zero-jedynkowych o długości n, w których liczba zer jest równa liczbie jedynek i w każdym początkowym (spójnym) podciągu liczba zer >= liczby jedynek.

Nie wiem, czy dobrze rozumiem. oznacza długość ciągu? Jeżeli tak, to wtedy w tym ciągu musi być zer i tyle samo jedynek, wobec tego robisz dynamika:
Dla -tej pozycji ciągu trzymasz tablicę wartości mówiącą ile jest ciągów długości , w których jest o więcej zer niż jedynek.
Następnie dla -ej pozycji łatwo aktualizujesz tę tablicę w czasie .
Całkowita złożoność to czyli

Aby spełnić warunek - "liczba zer jest równa liczbie jedynek" jest oczywistym że n musi być parzysta.
Ale czy warunek - "w każdym początkowym (spójnym) podciągu liczba zer >= liczby jedynek" - również dotyczy wyłącznie parzystych długości podciągów?
Prościej mówiąc, czy dla n=2 ciąg 10 jest "poprawny" czy nie?

Każdy to każdy, warunek "liczba zer >= liczby jedynek" dotyczy wszystkich podciągów. W szczególności, każdy akceptowany ciąg musi się rozpoczynać od 0 i kończyć 1.

Jak na razie machnąłem takie coś:

#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

bool isok(const string &str)
  {
   unsigned S=0,U=0;
   for(char ch:str)
     {
      if(ch=='1') ++S; else ++U;
      if(S>U) return false;
     }
   return (S==U);
  }

int main()
  {
   string str;
   for(unsigned n=2;;n+=2)
     {
      str+="01";
      sort(begin(str),end(str));
      unsigned count=0;
      while(true)
        {
         if(isok(str))
           {
            ++count;
            //cout<<"\t\t"<<n<<' '<<count<<' '<<str<<endl;
           }
         if(!next_permutation(begin(str),end(str))) break;
        }
      cerr<<n<<' '<<count<<endl;
     }
   return 0;
  }

w nadzieje coś zauważyć, ale niestety, może ktoś inny coś zauważy.

#include <iostream>
using namespace std;

const int n = 8;
const int k = n / 2;
int current[k+1];
int newState[k+1];

int main() {
	current[0] = 1; // At start we have one sequence with zero more zeroes than ones (it is an empty sequence)
	for(int i=1;i<=n;++i){
		for(int j=0;j<=k;++j){
			newState[j] = 0;
			if(j < k) newState[j] += current[j+1]; // Extend sequence by '1' and decrement the difference between zeroes and ones
			if(j > 0 && (i - 1 + j - 1)/2 < k) newState[j] += current[j-1]; // Extend sequence by '0' and increment the difference between zeroes and ones. We can do that only if numbers of zeroes in previous sequence is less than k
		}
		
		for(int j=0;j<=k;++j){
			current[j] = newState[j];
		}
	}
	printf("%d\n", current[0]);
	return 0;
}