Sum of Inversions in Bitmask of Length N

Правка en2, от vamaddur, 2017-07-20 14:16:31

Given a positive integer N, calculate the sum of inversions in every bitmask of length N.

For example, if N = 2, our masks are 00 (0 inversions), 01 (0 inversions), 10 (1 inversion), and 11 (0 inversions). We output 1.

For example, if N = 3, our masks are 000 (0 inversions), 001 (0 inversions), 010 (1 inversion), 011 (0 inversions), 100 (2 inversions), 101 (1 inversion), 110 (2 inversions), and 111 (0 inversions). We output 0+0+1+0+2+1+2+0 = 6.

How can I do this efficiently?

Please help, and thanks in advance!

Теги combinatorics, bitmask

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский vamaddur 2017-07-20 14:16:31 2 Tiny change: '+1+0+2+1+2 = 6.\n\nH' -> '+1+0+2+1+2+0 = 6.\n\nH'
en1 Английский vamaddur 2017-07-20 14:14:14 565 Initial revision (published)