Suppose we have an array A with first n natural numbers. We have to find how many sequences (S1) can we get after exact k adjacent swaps on A? And how many sequences (S2) can we get after at most k swaps on A? Here the adjacent swap means swapping elements at index i and i+1. https://www.tutorialspoint.com/prog...djacent-k-swaps-and-at-most-k-swaps-in-python Why we look sum of elements? Why sum of elements is the number of permuations? p = 10^9+7 A := an array with only one element 1 C := an array with only one element 1 for n in range 2 to n+1, do B := A, A := an array with only one element 1 D := C, C := an array with only one element 1 for x in range 1 to minimum of (k+1 and sum of all numbers from 1 to n) insert(last element of A + (B[x] when x < size of B otherwise 0) - (B[x-n] when 0 <= x-n otherwise 0)) mod p) at the end of A for x in range 1 to n-2, do insert ((D[x]+(n-1)*D[x-1]) mod p) at the end of C insert (n * last element of D) mod p at the end of C return sum of all elements of A[from index k mod 2 to k]) mod p and C[minimum of n-1 and k] Continue reading...
