Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import qualified Data.Vector.Unboxed as U
- import Data.Vector.Unboxed ( (!) )
- import qualified Data.Vector.Unboxed.Mutable as UM
- import Control.Monad.ST
- import Control.Monad
- base = 10 ^ 9 + 7 :: Int
- maxL = 3 * 10 ^ 5 :: Int
- n *% m = (n * m) `mod` base
- facs = U.scanl' (*%) 1 $ U.generate maxL (+ 1)
- invs = U.create f
- where
- f :: ST s (UM.MVector s Int)
- f = do
- v <- UM.new maxL
- UM.write v 0 1
- UM.write v 1 1
- forM_ [2 .. UM.length v - 1] $ \i -> do
- let (q, r) = divMod base i
- vr <- UM.read v r
- UM.write v i (base - vr * q `mod` base)
- return v
- facinvs = U.tail $ U.scanl' (*%) 1 invs
- combmod n k
- | n < k
- = 0
- | n < 0 || k < 0
- = 0
- | otherwise
- = facs ! n * (facinvs ! k * facinvs ! (n - k) `mod` base) `mod` base
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement