# CP\_05 Editorial

**URL:** <https://discuss.codechef.com/t/cp-05-editorial/100427>\
**Category:** editorial\
**Tags:** construction, dynamic-programming\
**Created:** [April 5, 2022, 4:57pm UTC](https://discuss.codechef.com/t/cp-05-editorial/100427 "2022-04-05T16:57:42Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![saurav1717](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@saurav1717](https://discuss.codechef.com/u/saurav1717)\
**Post date:** [April 5, 2022, 4:57pm UTC](https://discuss.codechef.com/t/cp-05-editorial/100427/1 "2022-04-05T16:57:42Z")

</div>

**Problem link**

[Click here](https://www.codechef.com/SPY22022/problems/CP_05)

**Difficulty**

Hard

**Solution**

mex array obtained from any permutation of a will be satisfying the following conditions

1. mex is non-decreasing
2. mex[i] \leq i (1-based indexing)
3. mex[n] = n

Number of sequences satisfying the above mentioned conditions can be easily calculated using dynamic programming in O(N^2).  
Lets define dp[i][j] as the number of sequences of length i satisfying the above mentioned conditions and having the i^{th} element equal to j, then the we can say :

1. dp[i][j] = \sum\_{k=0}^{j}dp[i-1][k] for j \leq i.
2. dp[i][j] = 0 for j\>i.

Note that if the last element of the permutation is x then this implies that mex[n-1] = x. So the number of distinct mex arrays in that case will be equal to dp[n-1][x]. So we basically have to print just the values of dp[n-1][0], dp[n-1][1]...dp[n-1][n-1].

**Code**

```auto
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod ll(1e9+7)
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	const int N=2000;
	ll dp[N+1][N+1];
	memset(dp,0,sizeof(dp));
	dp[0][0]=1;
	for(int i=1; i<=N; i++){
		ll sum=0;
		for(int j=0; j<=i; j++){
			sum+=dp[i-1][j];
			sum%=mod;
			dp[i][j]+=sum;
			dp[i][j]%=mod;
		}
	}
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		cin>>n;
		assert(n<=2000);
		for(int i=0; i<n; i++)
		 cout<<dp[n-1][i]<<" ";
		cout<<"\n";
	}
	return 0;
}

```