Approach

We will solve two parts separately. First lets find the min number of moves.
Let n be the size of s and m be the size of t.

Minimum number of moves.

Let ans[l][r] denote minimum number of moves to delete all occurrence of t in s[l]...s[r].
1. if there is no index j, in [l,r] such that j+m-1 < r and s[j...j+m-1] == t then ans[l][r] = 0.
2. else for all j's described above ans[l][r] = min(ans[l][r], ans[l][j-1] + 1 + ans[j+m][r])
The minimum number of moves are ans[0][n-1].
Let call this answer a1.

Number of ways to achieve those minimum number of moves.

Let's store all index j such that s[j-m+1....j] == t, in array validEnd.

Observations

1. A move deletes a sub-array and we can only work with last deleted index of that sub-array, as last deleted index completely defines a move.
   1.1. When we talk about deletion of index we only talk about last deleted index.
2. We try to make the string s, valid upto index i.

dp[i][j][0] : No of vaild sequences upto index i, using j moves and not deleting index i.
dp[i][j][1] : No of vaild sequences upto index i, using j moves and deleting index i.

Observe that we will delete index i only if i belongs to validEnd.

Case 1 : i belongs to vaildEnd

1. We can delete s[i-m+1...i] such that s upto index i-m has already been made valid.
   dp[i][j][1] = dp[i-m][j-1][0] + dp[i-m][j-1][1].
2. Or we will not delete i if some previous deletion already has made it impossible to pair s[i-m+1...i], which is just saying that total ways such that using j operations some index k such thati-m+1 <= k < i was deleted. dp[i][j][0] += dp[k][j][1] for all i-m+1 <= k < i.
   
   

Case 2 : i does not belong to vaildEnd

we will never delete i, dp[i][j][1] = 0, and
dp[i][j][0] = dp[i-1][j][1] + dp[i-1][j][0]

Finally total number of valid sequences are dp[n-1][a1][1] + dp[n-1][a1][0].

CODE

The Problem In Discussion is : https://codeforces.com/contest/1839/problem/D

Observations:
- The solution will be decreasing.
- The operation in question requires that we remove elements adjacent to zeroes, and then put them in the array anywhere.
- The trick is that we will not do the put, as we can put element anywhere we assume that we put it at the most optimal position, and we don't have to operate on it again.
- So we remove some elements adjacent to zeroes such that remaining elements form an increasing sub-sequence.
- Removed element will be placed optimally at their desired position. - Say you place some zeroes then each zero removes some contiguous sub-array, the 0 is present in this sub-array and sub-arrays of two zeroes don't overlap.
- A sub-array that zero removes, give cost equal to the number of elements in the sub-array.
- Now it is equivalent that each zero is present in the starting of the sub-array that it is removing.
- So this can be solved with dp.
- This problem is very identical to LIS.
- In fact answer for the last query is always n — size_of_lis of the array.


State of dp
dp[i][k][2]:
1. dp[i][k][0] -> minimum no of removed elements upto index i such that you have used k zeros and i'th element is not removed.
2. dp[i][k][1] -> minimum no of removed elements upto index i such that you have used k zeroes and i'th element is removed.
'
Transitions:
1. If we are removing the i'th element, and we have used k zeroes, then, we are talking about dp[i][k][1], the transition would be :
— that we removed the (i-1)th element and we did it in k zeroes so we can continue the removal so dp[i][k][1] be dp[i-1][k][1] + 1 (as we removed the i'th element)
— that we didn't remove the (i-1)th element, so we have to place a zero just before the i'th element so we can remove it. So dp[i][k][1] = dp[i-1][k-1][0] + 1 .


2. If we are not removing the i'th element then we will find a previous element that we have not removed and
that element must be less then i'th element. (Because we have to maintain the sequence in increasing order).
So for all x < i, such that v[x] < v[i] we can say dp[i][j][0] = dp[x][j-1]][0] + (i-x-1 (this term is no. of elements between x and i)).
— there is a special case if i-x-1 is zero means that x is just the prev element of i, then we don't have to give j-1 zeroes before the x th index. so we can say dp[i][j][0] = dp[x][j][0].

Code
https://codeforces.com/contest/1839/submission/216192185