SP28599 BDOI16C - Counting Magical Permutatitons

**Counting Permutations** In a planet far away from Earth, there is a beautiful country named Magicland. The children of this country play a lot of interesting games with numbers. One of the most popular games is called Inversion. In this game, you will be given numbers from 1 to N. They are given in a certain order. You need to calculate all the inversions in the given permutation of the numbers. S/he who can say it first correctly wins the game. An inversion occurs when there exists a pair of indices i and j such that i < j and given number at i-th position is greater than the number at j-th position. For example, let us consider a permutation of numbers 1 to 5: 5, 1, 4, 2, 3. This permutation has the following inversions: (5, 1), (5, 4), (5, 2), (5, 3), (4, 2), (4, 3). Therefore, the number of inversion will be 6. The first person to tell this number correctly will win this game. For this problem, we want to know how many permutations of the numbers 1, 2, .., N will have at least K inversions. A permutation X is different from another permutation Y if there exists some _i (1

N/A

N/A