Problem link
Difficulty
Hard
Solution
mex array obtained from any permutation of a will be satisfying the following conditions
- mex is non-decreasing
- mex[i] \leq i (1-based indexing)
- 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 :
- dp[i][j] = \sum_{k=0}^{j}dp[i-1][k] for j \leq i.
- 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
#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;
}