程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫

ai-PERMS

編輯:編程解疑
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

最佳回答:


http://blog.csdn.net/r1986799047/article/details/50074867

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved