# PROBLEM LINK:

*Author* - xenon_shivam

*tester* - imranasuman

# DIFFICULTY:

MEDIUM.

# PREREQUISITES:

DP, Math.

# PROBLEM:

There are two type of bacterias *X* and *Y*. X will always reproduce and Y can’t. Given a string consist of X and Y only, task is to guess the all possible valid generations of bacteria. Bacteria can also come on the slit from an external source.

# EXPLANATION:

This problem can be solved using dynamic programming.

First thing that is very clear, if a string ends with bacteria *X* at it last then it is considered to be a wrong data set and you have to print -*1* for that.

Now, let’s consider all possible generations which end with a certain type of bacteria at a certain depth from its root. Dynamic programming state will be an array *dp* [ *i* ][ *j* ] which stores the number of such generations ending with bacteria *i* at depth *j* .

The starting state is a one-dimensional array for *i* = 0. There is exactly one generation which consists of the first bacteria only, and its last bacteria has depth 0. Depth 0 refers that it is a bacteria from an external source.

The recurrent formula can be figured out from the description of the statements. When we add bacteria *i* + 1, its possible depths depend on the possible depths of bacteria *i* and on the type of bacteria (*X* or *Y*) *i* . If bacteria *i* is a *X*, bacteria *i* + 1 must have depth one greater than the depth of bacteria *i* , so *dp* [ *i* + 1][0] = 0 and *dp* [ *i* + 1][ *j* ] = *dp* [ *i* ][ *j* - 1] for *j* > 0. If bacteria *i* is a *Y*, bacteria *i* + 1 can belong to the family of any *X* before it, and have any depth from 0 to the depth of bacteria *i* . If we denote the depth of bacteria *i* (type *Y*) as *k* , the depth of bacteria *i* + 1 as *j* , we need to sum over all cases where *k* ≥ *j* :

**dp[i+1][j] =** Summation of k (from j to N-1) **dp[i][k]**

The answer to the task is the total number of generations which end with the last bacteria (Y of course)at any depth: **Summation of k (from 0 to N-1) dp[N-1][k]**

The complexity of this solution is *O* ( *N*^2).

# SOLUTIONS:

## Solution

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

const int mod = 1000000007;

void solve() {

ll n, i, j, m, q, type, l, r, x, k;

string s;

cin >> s;

n = s.size();

if (s[n - 1] == ‘X’) {

cout << -1 << “\n”;

return;

}

vector<vector> dp(n + 5, vector(n + 5, 0)), S(n + 5, vector(n + 5, 0));

dp[0][0] = 1;

for (i = 1; i <= n; i++) {

for (j = n; j >= 0; --j) {

S[i - 1][j] = S[i - 1][j + 1] + dp[i - 1][j];

S[i - 1][j] %= mod;

}

for (j = 0; j <= n; j++) {

if (j > 0 && s[i - 1] == ‘X’) {

dp[i][j] = dp[i - 1][j - 1];

} else {

if (s[i - 1] == ‘X’)

continue;

dp[i][j] = S[i - 1][j];

}

}

}

```
cout << dp[n][0] << "\n";
```

}

bool imp = true;

int main() {

fio;

int t = 1;

if (imp)cin >> t;

int m = t;

while (t–) {

solve();

}

return 0;

}