The order of the operations don’t matter since all the elements are unique and permutation of first N natural numbers. So let’s say you have an array of n integers:
[A0, A1, A2…An-1]
Let’s say I select the first two numbers from the list and apply the formula
A0 + A1 + A0A1 = X (let)
I could then remove these two elements and store this result as the first element (since the order doesn’t matter).
Now my list reduces to:
Now if I’m to apply it to the first two elements again, you can see that I’m using the previously computed result in the current calculation,
which smells like DP. You don’t in fact need to create a list here since we can treat a[i] as i as per the given problem.
So to calculate the result at the ith position (dp[i]), I use X = dp[i-1], Y = i and obtain the recurrence, which you can then preprocess it in O(n) and answer each test case in O(1).
As for the base condition, our recurrence depends on one previous term so we’ll need one base condition. The problem asks us to select two integers, but what if we have only one integer to begin with? That should be 1 as per the problem and the end of the operations. The recurrence has already been mentioned by rgkbitw, but I’ll write it once again. Take care of the overflow.
dp1 = 1 (assuming 1 based indexing)
dpi = (dpi-1 + i + i*dpi-1) % MOD
Final Complexity: O(n+t)