Submission #11456949

Source Code Expand

import           Data.Bits
import qualified Data.ByteString.Char8 as BS
import           Data.Maybe

-- compulte a^n `mod` p                                                                                                                      
modpow :: Int -> Int -> Int -> Int
modpow a n p =
    let modpow' a n res | n == 0    = res
                        | otherwise =
                            modpow' (a*a`mod`p)
                                    (n `shiftR` 1)
                                    (if (n .&. 1) == 1 then res * a `mod` p else res)
    in modpow' a n 1

-- compute a^(-1) `mod` p                                                                                                                    
modinv :: Int -> Int -> Int
modinv a p = modpow a (p-2) p

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine


main = do
  [n, a, b] <- getIntList

  let m = 10^9 + 7 :: Int

      fact i j | i == j = j
               | otherwise = i * fact (i-1) j `mod` m

      nCr n r = let num = fact n (n-r+1)
                    den = fact r 1
                in num * modinv den m `mod` m

      ans = (((modpow 2 n m - 1) `mod` m  - nCr n a) `mod` m  - nCr n b) `mod` m

  print ans

Submission Info

Submission Time
Task D - Bouquet
User unnohideyuki
Language Haskell (GHC 7.10.3)
Score 400
Code Size 1331 Byte
Status AC
Exec Time 32 ms
Memory 8204 KiB

Judge Result

Set Name All Sample
Score / Max Score 400 / 400 0 / 0
Status
AC × 22
AC × 2
Set Name Test Cases
All sample_01.txt, sample_02.txt, testcase_1.txt, testcase_10.txt, testcase_11.txt, testcase_12.txt, testcase_13.txt, testcase_14.txt, testcase_15.txt, testcase_16.txt, testcase_17.txt, testcase_18.txt, testcase_19.txt, testcase_2.txt, testcase_20.txt, testcase_3.txt, testcase_4.txt, testcase_5.txt, testcase_6.txt, testcase_7.txt, testcase_8.txt, testcase_9.txt
Sample sample_01.txt, sample_02.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 380 KiB
sample_02.txt AC 26 ms 8204 KiB
testcase_1.txt AC 1 ms 380 KiB
testcase_10.txt AC 16 ms 6908 KiB
testcase_11.txt AC 14 ms 4860 KiB
testcase_12.txt AC 17 ms 5884 KiB
testcase_13.txt AC 18 ms 6140 KiB
testcase_14.txt AC 8 ms 2684 KiB
testcase_15.txt AC 19 ms 7676 KiB
testcase_16.txt AC 10 ms 2940 KiB
testcase_17.txt AC 10 ms 2940 KiB
testcase_18.txt AC 17 ms 5884 KiB
testcase_19.txt AC 12 ms 4476 KiB
testcase_2.txt AC 1 ms 380 KiB
testcase_20.txt AC 30 ms 7804 KiB
testcase_3.txt AC 1 ms 380 KiB
testcase_4.txt AC 1 ms 380 KiB
testcase_5.txt AC 32 ms 7932 KiB
testcase_6.txt AC 13 ms 5116 KiB
testcase_7.txt AC 11 ms 3708 KiB
testcase_8.txt AC 24 ms 7420 KiB
testcase_9.txt AC 9 ms 3196 KiB