Permutaciones divisibles (OME2016 P5)

PorJosé A. Alonso 22-abril-202129-abril-2021

El enunciado del problema 5 de la OME (Olimpiada Matemática Española) del 2016 es

De entre todas las permutaciones (a(1), a(2),…, a(n)) del conjunto {1, 2,…, n},(n ≥ 1 entero), se consideran las que cumplen que 2(a(1) + a(2) +···+ a(m)) es divisible por m, para cada m = 1, 2,…, n. Calcular el número total de estas permutaciones.

Llamaremos permutaciones divisibles a las que cumplen la propiedad anterior. Por ejemplo, [2,3,4,1] es una permutación divisible de {1,2,3,4} ya que es una permutación del conjunto y se cumplen las condiciones:

2*2 = 4 es divisible por 1,
2*(2+3) = 10 es divisible por 2
2*(2+3+4) = 18 es divisible por 3.
2*(2+3+4+1) = 20 es divisible por 4.

Definir las siguientes funciones:

   permutacionesDivisibles  :: Integer -> [[Integer]]
   nPermutacionesDivisibles :: Integer -> Integer

1 2	permutacionesDivisibles :: Integer -> [[Integer]] nPermutacionesDivisibles :: Integer -> Integer

tales que

(permutacionesDivisibles n) es la lista de las permutaciones divisibles de {1,2,…,n}. Por ejemplo,

     λ> permutacionesDivisibles 2
     [[1,2],[2,1]]
     λ> permutacionesDivisibles 3
     [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
     λ> permutacionesDivisibles 4
     [[1,2,3,4],[1,3,2,4],[2,1,3,4],[2,3,1,4],[2,3,4,1],[2,4,3,1],
      [3,1,2,4],[3,2,1,4],[3,2,4,1],[3,4,2,1],[4,2,3,1],[4,3,2,1]]
     λ> length (permutacionesDivisibles 20)
     786432

λ> permutacionesDivisibles 2

[[1,2],[2,1]]

λ> permutacionesDivisibles 3

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

λ> permutacionesDivisibles 4

[[1,2,3,4],[1,3,2,4],[2,1,3,4],[2,3,1,4],[2,3,4,1],[2,4,3,1],

[3,1,2,4],[3,2,1,4],[3,2,4,1],[3,4,2,1],[4,2,3,1],[4,3,2,1]]

λ> length (permutacionesDivisibles 20)

786432

(nPermutacionesDivisibles n) es el número de permutaciones divisibles de {1,2,…,n}. Por ejemplo,

     nPermutacionesDivisibles 4  ==  12
     nPermutacionesDivisibles (10^8) `mod` (10^9)  ==  340332032

1 2	nPermutacionesDivisibles 4 == 12 nPermutacionesDivisibles (10^8) `mod` (10^9) == 340332032

Soluciones

import Data.List (genericLength, permutations, sort)

-- 1ª definición de permutacionesDivisibles
-- ========================================

permutacionesDivisibles :: Integer -> [[Integer]]
permutacionesDivisibles n =
  sort (filter aux (permutations [1..n]))
  where
    aux xs = and [(2*x) `mod` n == 0 | (x,n) <- zip (sumasParciales xs) [1..]]

-- (sumasParciales xs) es la lista de las suas parciales de xs. Por ejemplo,
--    sumasParciales [1..9]  ==  [1,3,6,10,15,21,28,36,45]
sumasParciales :: [Integer] -> [Integer]
sumasParciales = scanl1 (+)

-- 2ª definición de permutacionesDivisibles
-- ========================================

permutacionesDivisibles2 :: Integer -> [[Integer]]
permutacionesDivisibles2 = sort . aux
  where aux n
          | n < 4     = permutations [1..n]
          | otherwise = [xs ++ [n] | xs <- xss] ++
                        [map (+1) xs ++ [1] | xs <- xss]
          where xss = aux (n-1)

-- Comprobación de equivalencia
-- ============================

-- La comprobación para los n primeros valores es
--    λ> and [permutacionesDivisibles2 n == permutacionesDivisibles n | n <- [1..9]]
--    True

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> length (permutacionesDivisibles 10)
--    768
--    (8.42 secs, 10,420,281,776 bytes)
--    λ> length (permutacionesDivisibles2 10)
--    768
--    (0.02 secs, 2,250,152 bytes)
--
--    λ> length (permutacionesDivisibles2 20)
--    786432
--    (14.33 secs, 4,458,839,736 bytes)

-- 1ª definición de nPermutacionesDivisibles
-- =========================================

--    nPermutacionesDivisibles 5  ==  24
nPermutacionesDivisibles :: Integer -> Integer
nPermutacionesDivisibles =
  genericLength . permutacionesDivisibles

-- 2ª definición de nPermutacionesDivisibles
-- =========================================

nPermutacionesDivisibles2 :: Integer -> Integer
nPermutacionesDivisibles2 =
  genericLength . permutacionesDivisibles2

-- 3ª definición de nPermutacionesDivisibles
-- =========================================

-- Observando los siguientes cálculos:
--    λ> [nPermutacionesDivisibles2 n | n <- [1..12]]
--    [1,2,6,12,24,48,96,192,384,768,1536,3072]
--    λ> 1 : 2 : [3*2^(n-2) | n <- [3..12]]
--    [1,2,6,12,24,48,96,192,384,768,1536,3072]

nPermutacionesDivisibles3 :: Integer -> Integer
nPermutacionesDivisibles3 n
  | n < 3     = n
  | otherwise = 3*2^(n-2)

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> nPermutacionesDivisibles 10
--    768
--    (7.95 secs, 10,704,422,592 bytes)
--    λ> nPermutacionesDivisibles2 10
--    768
--    (0.01 secs, 2,269,872 bytes)
--    λ> nPermutacionesDivisibles3 10
--    768
--    (0.01 secs, 102,560 bytes)
--
--    λ> nPermutacionesDivisibles2 20
--    786432
--    (13.00 secs, 4,477,717,968 bytes)
--    λ> nPermutacionesDivisibles3 20
--    786432
--    (0.01 secs, 106,848 bytes)

import Data.List (genericLength, permutations, sort)

-- 1ª definición de permutacionesDivisibles

-- ========================================

permutacionesDivisibles :: Integer -> [[Integer]]

permutacionesDivisibles n =

sort (filter aux (permutations [1..n]))

where

aux xs = and [(2*x) `mod` n == 0 | (x,n) <- zip (sumasParciales xs) [1..]]

-- (sumasParciales xs) es la lista de las suas parciales de xs. Por ejemplo,

-- sumasParciales [1..9] == [1,3,6,10,15,21,28,36,45]

sumasParciales :: [Integer] -> [Integer]

sumasParciales = scanl1 (+)

-- 2ª definición de permutacionesDivisibles

-- ========================================

permutacionesDivisibles2 :: Integer -> [[Integer]]

permutacionesDivisibles2 = sort . aux

where aux n

| n < 4 = permutations [1..n]

| otherwise = [xs ++ [n] | xs <- xss] ++

[map (+1) xs ++ [1] | xs <- xss]

where xss = aux (n-1)

-- Comprobación de equivalencia

-- ============================

-- La comprobación para los n primeros valores es

-- λ> and [permutacionesDivisibles2 n == permutacionesDivisibles n | n <- [1..9]]

-- True

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> length (permutacionesDivisibles 10)

-- 768

-- (8.42 secs, 10,420,281,776 bytes)

-- λ> length (permutacionesDivisibles2 10)

-- 768

-- (0.02 secs, 2,250,152 bytes)

-- λ> length (permutacionesDivisibles2 20)

-- 786432

-- (14.33 secs, 4,458,839,736 bytes)

-- 1ª definición de nPermutacionesDivisibles

-- =========================================

-- nPermutacionesDivisibles 5 == 24

nPermutacionesDivisibles :: Integer -> Integer

nPermutacionesDivisibles =

genericLength . permutacionesDivisibles

-- 2ª definición de nPermutacionesDivisibles

-- =========================================

nPermutacionesDivisibles2 :: Integer -> Integer

nPermutacionesDivisibles2 =

genericLength . permutacionesDivisibles2

-- 3ª definición de nPermutacionesDivisibles

-- =========================================

-- Observando los siguientes cálculos:

-- λ> [nPermutacionesDivisibles2 n | n <- [1..12]]

-- [1,2,6,12,24,48,96,192,384,768,1536,3072]

-- λ> 1 : 2 : [3*2^(n-2) | n <- [3..12]]

-- [1,2,6,12,24,48,96,192,384,768,1536,3072]

nPermutacionesDivisibles3 :: Integer -> Integer

nPermutacionesDivisibles3 n

| n < 3 = n

| otherwise = 3*2^(n-2)

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> nPermutacionesDivisibles 10

-- 768

-- (7.95 secs, 10,704,422,592 bytes)

-- λ> nPermutacionesDivisibles2 10

-- 768

-- (0.01 secs, 2,269,872 bytes)

-- λ> nPermutacionesDivisibles3 10

-- 768

-- (0.01 secs, 102,560 bytes)

-- λ> nPermutacionesDivisibles2 20

-- 786432

-- (13.00 secs, 4,477,717,968 bytes)

-- λ> nPermutacionesDivisibles3 20

-- 786432

-- (0.01 secs, 106,848 bytes)

Nuevas soluciones

En los comentarios se pueden escribir nuevas soluciones.
El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

5 Comentarios

import Data.List

listaDivisible :: [Integer] -> Bool
listaDivisible xs = and [rem (2*(sum (genericTake n xs))) n == 0 | n<-[1..genericLength xs]]
        
permutacionesDivisibles  :: Integer -> [[Integer]]
permutacionesDivisibles n = [xs | xs<-permutations [1..n] , listaDivisible xs]

nPermutacionesDivisibles :: Integer -> Integer
nPermutacionesDivisibles n = genericLength (permutacionesDivisibles n)

import Data.List

listaDivisible :: [Integer] -> Bool

listaDivisible xs = and [rem (2*(sum (genericTake n xs))) n == 0 | n<-[1..genericLength xs]]

permutacionesDivisibles :: Integer -> [[Integer]]

permutacionesDivisibles n = [xs | xs<-permutations [1..n] , listaDivisible xs]

nPermutacionesDivisibles :: Integer -> Integer

nPermutacionesDivisibles n = genericLength (permutacionesDivisibles n)

Responder

{-

  Una propiedad de poda de recursión puede ser que:

         2 a1 = 1 · k1
  2 a1 + 2 a2 = 2 · k2
          ... = ...

           2 a{i-1} + ... = (i-1) · k{i-1}
  2 a{i} + 2 a{i-1} + ... =  i    · k{i  }

  Restando

  2 a{i} + (i-1) · k{i-1} = i · k{i}

  Es decir, para cada nuevo sumando se debe cumplir que:

  k1   = 2 a1
  k{i} = (2 a{i} + (i-1) · k{i-1}) / i

-}
permutacionesDivisibles :: Integer -> [[Integer]]
permutacionesDivisibles n = rec [] [1..n] 1 0
  where rec rs [] _ _ = return rs
        rec rs xs i k = do
          a <- xs
          case (2 * a + (i - 1) * k) `divMod` i of
            (k', 0) -> rec (a:rs) (filter (a /= ) xs) (i + 1) k'
            _       -> []

{-

*Main> mapM_ (print . length . permutacionesDivisibles) [1..]
1
2
6
12
24
48
96
192
384
768
1536
3072
6144
12288
24576
49152
98304
196608
393216
786432
1572864
3145728
...

-}

-- No caigo de exactamente porqué, pero siguen la progresión:
nPermutacionesDivisibles :: Integer -> Integer
nPermutacionesDivisibles 1 = 1
nPermutacionesDivisibles 2 = 2
nPermutacionesDivisibles 3 = 6
nPermutacionesDivisibles n = 2 * nPermutacionesDivisibles (n - 1)

-- que para n>=3 puede escribirse como 6 * 2^(n - 3)

Una propiedad de poda de recursión puede ser que:

2 a1 = 1 · k1

2 a1 + 2 a2 = 2 · k2

... = ...

2 a{i-1} + ... = (i-1) · k{i-1}

2 a{i} + 2 a{i-1} + ... = i · k{i }

Restando

2 a{i} + (i-1) · k{i-1} = i · k{i}

Es decir, para cada nuevo sumando se debe cumplir que:

k1 = 2 a1

k{i} = (2 a{i} + (i-1) · k{i-1}) / i

permutacionesDivisibles :: Integer -> [[Integer]]

permutacionesDivisibles n = rec [] [1..n] 1 0

where rec rs [] _ _ = return rs

rec rs xs i k = do

a <- xs

case (2 * a + (i - 1) * k) `divMod` i of

(k', 0) -> rec (a:rs) (filter (a /= ) xs) (i + 1) k'

_ -> []

*Main> mapM_ (print . length . permutacionesDivisibles) [1..]

192

384

768

1536

3072

6144

12288

24576

49152

98304

196608

393216

786432

1572864

3145728

...

-- No caigo de exactamente porqué, pero siguen la progresión:

nPermutacionesDivisibles :: Integer -> Integer

nPermutacionesDivisibles 1 = 1

nPermutacionesDivisibles 2 = 2

nPermutacionesDivisibles 3 = 6

nPermutacionesDivisibles n = 2 * nPermutacionesDivisibles (n - 1)

-- que para n>=3 puede escribirse como 6 * 2^(n - 3)

Responder

-- Perdón, buscando la razón me perdí, no importa mucho pero más simple checar la suma directamente
permutacionesDivisibles :: Integer -> [[Integer]]
permutacionesDivisibles n = rec [] [1..n] 1 0
  where rec rs [] _ _ = return rs
        rec rs xs i s = do
          a <- xs
          let s' = 2 * a + s
          guard $ s' `mod` i == 0
          rec (a:rs) (filter (a /= ) xs) (i + 1) s'

-- Perdón, buscando la razón me perdí, no importa mucho pero más simple checar la suma directamente

permutacionesDivisibles :: Integer -> [[Integer]]

permutacionesDivisibles n = rec [] [1..n] 1 0

where rec rs [] _ _ = return rs

rec rs xs i s = do

a <- xs

let s' = 2 * a + s

guard $ s' `mod` i == 0

rec (a:rs) (filter (a /= ) xs) (i + 1) s'

Responder

Sabiendo que para n>3 son las de n-1 transformadas pueden generarse directamente (sin poda)

todasPermutacionesDivisibles :: [[[Integer]]]
todasPermutacionesDivisibles = [[1]]:[[1,2],[2,1]]:rec 4 (permutations [1..3])
  where rec z xs = xs: rec (z+1) (map (++[z]) xs ++ map ((++[1]).(map (+1))) xs)

permutacionesDivisibles :: Integer -> [[Integer]]
permutacionesDivisibles n = todasPermutacionesDivisibles!!(fromInteger n - 1)

{-

*Main> length $ permutacionesDivisibles 27
100663296
(26.08 secs, 23,354,014,440 bytes)

-}

todasPermutacionesDivisibles :: [[[Integer]]]

todasPermutacionesDivisibles = [[1]]:[[1,2],[2,1]]:rec 4 (permutations [1..3])

where rec z xs = xs: rec (z+1) (map (++[z]) xs ++ map ((++[1]).(map (+1))) xs)

permutacionesDivisibles :: Integer -> [[Integer]]

permutacionesDivisibles n = todasPermutacionesDivisibles!!(fromInteger n - 1)

*Main> length $ permutacionesDivisibles 27

100663296

(26.08 secs, 23,354,014,440 bytes)

Responder

import Data.List
 
listaDivisible :: [Integer] -> Bool
listaDivisible xs = and [rem (2*(sum (genericTake n xs))) n == 0 | n<-[1..genericLength xs]]
 
permutacionesDivisibles  :: Integer -> [[Integer]]
permutacionesDivisibles n = [xs | xs<-permutations [1..n] , listaDivisible xs]
 
nPermutacionesDivisibles :: Integer -> Integer
nPermutacionesDivisibles n = genericLength (permutacionesDivisibles n)

-- permutacionesDivisibles 3
-- [[1,2,3],[2,1,3],[3,2,1],[2,3,1],[3,1,2],[1,3,2]]
-- permutacionesDivisibles 4
-- [[1,2,3,4],[2,1,3,4],[3,2,1,4],[2,3,1,4],[3,1,2,4],[1,3,2,4],
--  [4,3,2,1],[3,4,2,1],[3,2,4,1],[4,2,3,1],[2,4,3,1],[2,3,4,1]]

-- Reordenando:
-- [[1,2,3,4],[2,1,3,4],[3,2,1,4],[2,3,1,4],[3,1,2,4],[1,3,2,4],
--  [2,3,4,1],[3,2,4,1],[4,3,2,1],[3,4,2,1],[4,2,3,1],[2,4,3,1]]

-- Parece que sigue el patrón siguiente, a partir de n = 4:
-- 

permutacionesDivisibles2  :: Integer -> [[Integer]]
permutacionesDivisibles2 1 = permutations [1]
permutacionesDivisibles2 2 = permutations [1,2]
permutacionesDivisibles2 3 = permutations [1,2,3]
permutacionesDivisibles2 n = map (++[n]) xss ++ map f xss
  where xss = permutacionesDivisibles2 (n-1)
        f xs = (map (+1) xs) ++ [1]

-- length (permutacionesDivisibles2 20) == 786432

-- Usando evaluación perezosa

sucPerDiv :: [[[Integer]]]
sucPerDiv = (permutations [1]):(permutations [1,2]): iterate g (permutations [1,2,3])
  where g xss = map (++[n]) xss ++ map f xss
          where n = 1 + genericLength (head xss)
                f xs = (map (+1) xs) ++ [1]

permutacionesDivisibles3  :: Integer -> [[Integer]]
permutacionesDivisibles3 n = sucPerDiv `genericIndex` (n-1)

-- Comparación de eficiencia:

-- length (permutacionesDivisibles2 20) == 786432
-- (0.18 secs, 182,535,376 bytes)
-- length (permutacionesDivisibles3 20) == 786432
-- (0.27 secs, 182,538,936 bytes)

-- Segunda definición del número de permutaciones:

sucNumPerDiv :: [Integer]
sucNumPerDiv = 1:2:iterate (*2) 6

nPermutacionesDivisibles2 :: Integer -> Integer
nPermutacionesDivisibles2 n = sucNumPerDiv `genericIndex` (n-1)


-- Observación:

-- take 20 sucNumPerDiv
-- [1,2,6,12,24,48,96,192,384,768,1536,3072,6144,12288,24576,49152,98304,196608,393216,786432]
-- λ> import Data.Numbers.Primes
-- λ> map primeFactors [1,2,6,12,24,48,96,192,384,768,1536,3072,6144,12288,24576,49152,98304,196608,393216,786432]
-- [[],[2],[2,3],[2,2,3],[2,2,2,3],[2,2,2,2,3],[2,2,2,2,2,3],[2,2,2,2,2,2,3],[2,2,2,2,2,2,2,3],[2,2,2,2,2,2,2,2,3],
--  [2,2,2,2,2,2,2,2,2,3],[2,2,2,2,2,2,2,2,2,2,3],[2,2,2,2,2,2,2,2,2,2,2,3],[2,2,2,2,2,2,2,2,2,2,2,2,3],
--  [2,2,2,2,2,2,2,2,2,2,2,2,2,3],[2,2,2,2,2,2,2,2,2,2,2,2,2,2,3],[2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3],
--  [2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3],[2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3],[2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3]]

-- Tercera definición:

nPermutacionesDivisibles3 :: Integer -> Integer
nPermutacionesDivisibles3 1 = 1
nPermutacionesDivisibles3 2 = 2
nPermutacionesDivisibles3 n = 3*2^(n-2)

-- nPermutacionesDivisibles3 (10^8) `mod` (10^9) == 340332032

import Data.List

listaDivisible :: [Integer] -> Bool

listaDivisible xs = and [rem (2*(sum (genericTake n xs))) n == 0 | n<-[1..genericLength xs]]

permutacionesDivisibles :: Integer -> [[Integer]]

permutacionesDivisibles n = [xs | xs<-permutations [1..n] , listaDivisible xs]

nPermutacionesDivisibles :: Integer -> Integer

nPermutacionesDivisibles n = genericLength (permutacionesDivisibles n)

-- permutacionesDivisibles 3

-- [[1,2,3],[2,1,3],[3,2,1],[2,3,1],[3,1,2],[1,3,2]]

-- permutacionesDivisibles 4

-- [[1,2,3,4],[2,1,3,4],[3,2,1,4],[2,3,1,4],[3,1,2,4],[1,3,2,4],

-- [4,3,2,1],[3,4,2,1],[3,2,4,1],[4,2,3,1],[2,4,3,1],[2,3,4,1]]

-- Reordenando:

-- [[1,2,3,4],[2,1,3,4],[3,2,1,4],[2,3,1,4],[3,1,2,4],[1,3,2,4],

-- [2,3,4,1],[3,2,4,1],[4,3,2,1],[3,4,2,1],[4,2,3,1],[2,4,3,1]]

-- Parece que sigue el patrón siguiente, a partir de n = 4:

permutacionesDivisibles2 :: Integer -> [[Integer]]

permutacionesDivisibles2 1 = permutations [1]

permutacionesDivisibles2 2 = permutations [1,2]

permutacionesDivisibles2 3 = permutations [1,2,3]

permutacionesDivisibles2 n = map (++[n]) xss ++ map f xss

where xss = permutacionesDivisibles2 (n-1)

f xs = (map (+1) xs) ++ [1]

-- length (permutacionesDivisibles2 20) == 786432

-- Usando evaluación perezosa

sucPerDiv :: [[[Integer]]]

sucPerDiv = (permutations [1]):(permutations [1,2]): iterate g (permutations [1,2,3])

where g xss = map (++[n]) xss ++ map f xss

where n = 1 + genericLength (head xss)

f xs = (map (+1) xs) ++ [1]

permutacionesDivisibles3 :: Integer -> [[Integer]]

permutacionesDivisibles3 n = sucPerDiv `genericIndex` (n-1)

-- Comparación de eficiencia:

-- length (permutacionesDivisibles2 20) == 786432

-- (0.18 secs, 182,535,376 bytes)

-- length (permutacionesDivisibles3 20) == 786432

-- (0.27 secs, 182,538,936 bytes)

-- Segunda definición del número de permutaciones:

sucNumPerDiv :: [Integer]

sucNumPerDiv = 1:2:iterate (*2) 6

nPermutacionesDivisibles2 :: Integer -> Integer

nPermutacionesDivisibles2 n = sucNumPerDiv `genericIndex` (n-1)

-- Observación:

-- take 20 sucNumPerDiv

-- [1,2,6,12,24,48,96,192,384,768,1536,3072,6144,12288,24576,49152,98304,196608,393216,786432]

-- λ> import Data.Numbers.Primes

-- λ> map primeFactors [1,2,6,12,24,48,96,192,384,768,1536,3072,6144,12288,24576,49152,98304,196608,393216,786432]

-- [[],[2],[2,3],[2,2,3],[2,2,2,3],[2,2,2,2,3],[2,2,2,2,2,3],[2,2,2,2,2,2,3],[2,2,2,2,2,2,2,3],[2,2,2,2,2,2,2,2,3],

-- [2,2,2,2,2,2,2,2,2,3],[2,2,2,2,2,2,2,2,2,2,3],[2,2,2,2,2,2,2,2,2,2,2,3],[2,2,2,2,2,2,2,2,2,2,2,2,3],

-- [2,2,2,2,2,2,2,2,2,2,2,2,2,3],[2,2,2,2,2,2,2,2,2,2,2,2,2,2,3],[2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3],

-- [2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3],[2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3],[2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3]]

-- Tercera definición:

nPermutacionesDivisibles3 :: Integer -> Integer

nPermutacionesDivisibles3 1 = 1

nPermutacionesDivisibles3 2 = 2

nPermutacionesDivisibles3 n = 3*2^(n-2)

-- nPermutacionesDivisibles3 (10^8) `mod` (10^9) == 340332032

Responder

Permutaciones divisibles (OME2016 P5)

Soluciones

Nuevas soluciones

5 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Nuevas soluciones

Se puede imprimir o compartir con

5 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico