Problem 194

Coloured Configurations
Problem 194 - Project Euler
困難は分割せよ．ということで，それぞれのユニットごとの塗り分けパターンを考えてみた．
結果．

choose :: (Integral a) => a -> a -> a
choose n r = div (product [n-r+1..n]) $ product [1..r]

p194 :: Integer -> Integer -> Integer -> Integer 
p194 a b n = n * (n-1) * pa^a  * pb^b * choose (a+b) a
    where pa = sum.zipWith (*) [4,54,198,264,120] $ cs
          pb = sum.zipWith (*) [6,76,240,288,120] $ cs
          cs = map (choose (n-2)) $ [1..5]

main :: IO ()
main = print $ mod (p194 25 75 1984) (10^8)

[4,54,198,264,120]，[6,76,240,288,120]は使う色の数を決めたときの塗り分けかた，のようなもの．
つぎの関数 pattern で求めた．

import Data.List ((\\),sort,nub,genericLength)

data Unit = A | B

step :: Unit -> Int -> [[Int]]
step u n = do
  a <- ds\\[1]
  c <- ds\\[2]
  b <- ds\\[a,c]
  x <- ds\\[1,a]
  y <- case u of
         A -> ds\\[2,c,x]
         B -> ds\\[c,x]
  return $ [1,2,a,b,c,x,y]
    where ds = [1..n]

embedding :: Unit -> Int -> Integer
embedding u n = genericLength.filter (==n).map (length.nub.sort).step u $ n

pattern :: Unit -> [Integer]
pattern u = map (embedding u) [3..7]

stepでのイメージ．

１　ｘ
　ａ
　ｂ
　ｃ
２　ｙ