結果

問題 No.2356 Back Door Tour in Four Seasons
ユーザー mtwtkmanmtwtkman
提出日時 2023-06-18 13:31:01
言語 Haskell
(9.8.2)
結果
TLE  
実行時間 -
コード長 2,535 bytes
コンパイル時間 2,002 ms
コンパイル使用メモリ 176,852 KB
実行使用メモリ 11,128 KB
最終ジャッジ日時 2023-09-08 09:27:01
合計ジャッジ時間 8,308 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
11,128 KB
testcase_01 AC 2 ms
6,672 KB
testcase_02 AC 3 ms
6,784 KB
testcase_03 AC 2 ms
6,808 KB
testcase_04 TLE -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.6.1/environments/default
[1 of 2] Compiling Main             ( Main.hs, Main.o )
[2 of 2] Linking a.out

ソースコード

diff # 

module Main where

-- https://yukicoder.me/problems/no/2356
split :: String -> [String]
split = go ("", [])
  where
    go :: (String, [String]) -> String -> [String]
    go (a, acc) "" = acc <> [a]
    go (a, acc) (' ' : xs) = go ("", acc <> [a]) xs
    go (a, acc) (x : xs) = go (a <> [x], acc) xs

prompt :: IO [String]
prompt = do split <$> getLine

promptN :: Int -> IO [[String]]
promptN n = go n []
  where
    go :: Int -> [[String]] -> IO [[String]]
    go 0 acc = return acc
    go n acc = do
      vs <- prompt
      go (n - 1) (acc <> [vs])

fixMod :: Int
fixMod = 998244353

pow :: Int -> Int -> Int -> Int
pow _ 0 _ = 1
pow x n m =
  let x' = x * x `mod` m
      n' = n `div` 2
      r = pow x' n' m
   in if odd n
        then (x * r) `mod` m
        else r

inv :: Int -> Int -> Int
inv x m = pow x (m - 2) m

extract :: [[String]] -> ([Char], [Int], Int)
extract = foldr f ([], [], 0)
  where
    f :: [String] -> ([Char], [Int], Int) -> ([Char], [Int], Int)
    f vs (ss, as, doorCount) =
      let s = head (head vs)
          a = read (last vs) :: Int
       in (s : ss, a : as, doorCount + a)

calcSeason :: Int -> [Char] -> [Int] -> (Int, Int, Int, Int)
calcSeason n ss as = go n ss as (0, 0, 0, 0)
  where
    go :: Int -> [Char] -> [Int] -> (Int, Int, Int, Int) -> (Int, Int, Int, Int)
    go 0 _ _ acc = acc
    go m (s : restS) (a : restA) (summer, fall, winter, spring) =
      let prd = pow (n - 1) a fixMod
          prd' = (prd + fixMod - pow (n - 2) a fixMod) `mod` fixMod
          prd'' = (prd' * inv (pow (n - 1) a fixMod) fixMod) `mod` fixMod
       in go
            (m - 1)
            restS
            restA
            ( case s of
                'U' -> ((summer + prd'') `mod` fixMod, fall, winter, spring)
                'F' -> (summer, (fall + prd'') `mod` fixMod, winter, spring)
                'W' -> (summer, fall, (winter + prd'') `mod` fixMod, spring)
                'P' -> (summer, fall, winter, spring + 1)
            )

solve :: Int -> Int -> Int -> Int -> Int -> Int -> Int
solve n doors summer fall winter spring =
  let a' = (1 * summer) `mod` fixMod
      a'' = (a' * fall) `mod` fixMod
      a''' = (a'' * winter) `mod` fixMod
      answer = (a''' * spring) `mod` fixMod
   in (answer * pow (n - 1) doors fixMod) `mod` fixMod

main :: IO ()
main = do
  inputN <- prompt
  let n = read (head inputN) :: Int
  vs <- promptN n
  let (ss, as, doorCount) = extract vs
      (summer, fall, winter, spring) = calcSeason n ss as
  print $ solve n doorCount summer fall winter spring
0