首页 > 专题系列 > Java解POJ > POJ 2323 PERMS [解题报告] Java
2013
11-11

POJ 2323 PERMS [解题报告] Java

PERMS

问题描述 :

Count the number of permutations that have a specific number of inversions.

Given a permutation a1, a2, a3,…, an of the n integers 1, 2, 3, …, n, an inversion is a pair (ai, aj) where i < j and ai > aj. The number of inversions in a permutation gives an indication on how “unsorted” a permutation is. If we wish to analyze the average running time of a sorting algorithm, it is often useful to know how many permutations of n objects will have a certain number of inversions.

In this problem you are asked to compute the number of permutations of n values that have exactly k inversions.

For example, if n = 3, there are 6 permutations with the indicated inversions as follows:

123			0 inversions


132 1 inversion (3 > 2)

213 1 inversion (2 > 1)

231 2 inversions (2 > 1, 3 > 1)

312 2 inversions (3 > 1, 3 > 2)

321 3 inversions (3 > 2, 3 > 1, 2 > 1)

Therefore, for the permutations of 3 things

  • 1 of them has 0 inversions
  • 2 of them have 1 inversion
  • 2 of them have 2 inversions
  • 1 of them has 3 inversions
  • 0 of them have 4 inversions
  • 0 of them have 5 inversions
  • etc.

输入:

The input consists one or more problems. The input for each problem is specified on a single line, giving the integer n (1 <= n <= 18) and a non-negative integer k (0 <= k <= 200). The end of input is specified by a line with n = k = 0.

输出:

For each problem, output the number of permutations of {1, …, n}with exactly k inversions.

样例输入:

3 0
3 1
3 2
3 3
4 2
4 10
13 23
18 80
0 0

样例输出:

1
2
2
1
5
0
46936280
184348859235088

解题代码:

//* @author:alpc12
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;


public class Main {

    public static void main(String[] args) throws FileNotFoundException {
        new Main().run();

    }
    
    BigInteger [][] dp;

    private void run() throws FileNotFoundException {
        Scanner cin = new Scanner(System.in);
        //Scanner cin = new Scanner(new BufferedReader(new FileReader("t.in")));
        dp = new BigInteger[19][201];
        for(int i = 0; i < 19; ++i) {
            Arrays.fill(dp[i], BigInteger.ZERO);
        }
        dp[1][0] = BigInteger.ONE;
        for(int i = 2; i < 19; ++i) {
            for(int j = 0; j <= (i-1)*i/2 && j < 201; ++j) {
                for(int k = j; k >= j-i+1 && k >= 0; --k) {
                    dp[i][j] = dp[i][j].add(dp[i-1][k]);
                }
            }
        }
        while(true) {
            int a = cin.nextInt(), b = cin.nextInt();
            if(a == 0 && b == 0)
                break;
            System.out.println(dp[a][b]);
        }
        
    }

}