Submission #41239917

---

Source Code Expand

import Control.Monad
import qualified Data.ByteString.Char8 as BS
import Data.Char
import Data.List

import Data.Array
import qualified Data.IntSet as IS

main = do
  [n,m] <- bsGetLnInts
  fs <- replicateM n (head <$> bsGetLnInts)
  let ans = abc017d n m fs
  print ans

bsGetLnInts :: IO [Int]
bsGetLnInts = unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine

abc017d :: Int -> Int -> [Int] -> Int
abc017d n m fs = count ! n
  where
    count = listArray (0,n) $ 1 : loop 0 1 1 IS.empty fs fs
    loop :: Int  -- k : 左端の位置
         -> Int  -- i : 右端、次に値を決めるcount[i]の位置
         -> Int  -- s : kからi-1までのcount[]の総和
         -> IS.IntSet -- is : k+1からiまでにある味の集合
         -> [Int]  -- fks : kの味、以降のリスト
         -> [Int]  -- fis : iの味、以降のリスト
         -> [Int]  -- 答え count[1]～count[N] の値を順に
    loop k i s is fks fis
-- 右の味が尽きたなら、全てを計算し終えた
      | null fis = []
-- 右の味が既にあるなら、左を縮める
      | IS.member fi is = loop (succ k) i (reg $ s - count ! k) (IS.delete fk is) (tail fks) fis
-- まだないなら、取り込んで伸びる。
      | otherwise = s : loop k (succ i) (reg $ s + s) (IS.insert fi is) fks (tail fis)
      where
        fi = head fis -- 次に加入する味
        fk = head fks -- 次に離脱する味

modBase = 1000000007
reg x = mod x modBase

Submission Info

Compile Error

Loaded package environment from /home/contestant/.ghc/x86_64-linux-8.8.3/environments/default

Judge Result