We know that:

So, one of the best ways to create the array A of length n, is:

A[i]=i, where 1<=i<=n

Time Complexity: O(n), per test case.

Space Complexity: O(1), per test case.

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        for(int i=1;i<=n;++i)
        	cout << i << " ";
        cout << '\n';
    }
    return 0;
}

Bitwise-XOR of any number, X with 0 is equal to the number itself (X).

So, if we set the first element of the Array A as X, and the next K-1 elements as 0, then we will have the XOR of first sub-array of length K, equal to X, which is required.

XOR(A[0],...,A[K-1]) = X

Now, if we set A[K] as A[0], then we will have XOR(A[1],...,A[K]) = X

Similarly, if we set A[K+1] as A[1], then we will have XOR(A[2],...,A[K+1]) = X

And continuing so, we can observe that the general formula can be described as below:

A[i] = X, when i%K==0 and 0<=i<=N-1

A[i] = 0, when i%K!=0 and 0<=i<=N-1

Time Complexity: O(N), per test case.

Space Complexity: O(K), per test case.

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--)
    {
        ll n,k,_xor;
        cin >> n >> k >> _xor;
        vector<ll> ans(k,0);
        ans[0]=_xor;
        for(int i=0;i<n;++i)
        	cout << ans[i%k] << " ";
        cout << '\n';
    }
    return 0;
}

Let DP[i][j] denote the number of possible arrays, where i denotes the Last (Smallest) number in the Array, and j denotes the Size of the Array.

If the size of the array is 1, no matter whatever is the value of i, the following equation will always be true:

DP[i][1] = 1

Observe here that, the last (smallest) element of array of size j will always be less than or equal to last (smallest) element of array of size j-1.

Using this observation, we can generalise the DP table as follows:

where 1<=i<=N and 2<=j<=K.

The above equation takes O(N*N*K) time, for calculating the whole DP Table.

So, we will use Suffix Sums, to calculate the DP Table, using the above formula, in O(N*K) time.

Time Complexity: O(N*K)

Space Complexity: O(N*K)

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define endl '\n'
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,k;
    cin >> n >> k;
    vector<vector<int>> dp(n+1,vector<int>(k+1));
    for(int i=1;i<=n;++i)
    {
    	dp[i][1]=1;
    }
    for(int i=n;i>=1;--i)
    {
        for(int j=2;j<=k;++j)
        {
            if(i==n)
                dp[i][j]=dp[i][j-1];
            else
                dp[i][j]=dp[i][j-1]+dp[i+1][j];
            dp[i][j]%=1000000007;
        }
    }
    ll ans=0;
    for(int i=1;i<=n;++i)
    {
        ans+=dp[i][k];
        ans%=1000000007;
    }  
    cout << ans << endl;
    return 0;
}