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
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でのイメージ.

1 x
 a
 b
 c
2 y