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 ith position is greater than the number at jth 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<=i<=N) for which the number in ith position is different in these two permutations.
Input
The first line of input file contains the number of test cases, T (1<=T<=50). Then T cases follow:
Each case consists of one line which contains two integers: N and K.
Constraint
For Easy version, 1<=N<=200 and 0<=K<=300.
For Hard version, 1<=N<=2000 and 0<=K<=3000.
Output
For each case, print “Case x: y” in a separate line, where x is the case number and y is the number of permutations with at least K inversions. As the number can be very large, print y modulo 10,007.
Sample Input 
Sample Output 
3 3 1 2 1 3 2 
Case 1: 5 Case 2: 1 Case 3: 3 
Problem Setter: Anindya Das
hide comments
wisfaq:
20161012 10:03:23
Permutatitons? 

Vipul Srivastava:
20161010 08:21:17
Last edit: 20161022 12:31:32 
Added by:  Rezwan 
Date:  20161005 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU 
Resource:  Bangladesh Olympiad on Informatics 2016 National; Problem Setter: Anindya Das 