How to solve this combinatorial problem?

Question

Combinatorics

I've been banging my head on the table for two hours now, how can I solve this? Duck still need to write a universal algorithm. Please help!!!

Answer 1

It is better to beat a pen on a piece of paper. Write a sample and think about how you would solve it manually.
In a string, you are only interested in the ones and the LENGTH of the string of zeros BETWEEN them.
If the units are in a row - there is one option to separate them.
If there is one zero between them, there are two options.
If two zeros - three options.
If there is one zero between the first and second ones, and two between the second and third, how many options are there?
Further myself.

Answer 2

Imagine your string, and draw sticks between two adjacent bits where the block boundary is. The question is in the task to count the number of ways to arrange these sticks correctly (there must be a stick at the very beginning and at the very end, between any neighboring sticks there is exactly one unit).
From the condition it turns out that between two ones, separated by some (maybe empty) number of zeros, there must be exactly one stick. Those. the boundaries of the arrangement of different sticks do not intersect. there is one between the first and second unit. one between the second and third, and so on.
So consider how many options to put a stick in front of each unit. It is necessary to calculate the distances between each pair of units and multiply. If there are no units at all, the answer is 0, if there is one, then 1.
Can be done in one pass if you remember where the previous unit was.

int64_t CountWaysToSplit(std::string s) {
  int last_one = -1;
  int64_t res = 1;
  for (int i = 0; i < s.length(); ++i) {
    if (s[i] == '1') {
      if (last_one >= 0) res *= i - last_one;
      last_one = i;
    }
  }
  return last_one >= 0 ? res : 0;
}