Submission #43767773

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import Data.Array
import Data.Bits
import Data.List
main = do
  n <- readLn
  as <- map read . words <$> getLine
  let ans = abc310f n as
  print ans
type State = Array Int Int -- 作れる数のビット集合 → 場合の数
abc310f :: Int -> [Int] -> Int
abc310f n as = divm answer denom
  where
    initial = accumArray (+) 0 (0,ub) [(0,1)]
    final = foldl' {-'-} step initial as
    answer = foldl' {-'-} addm 0 [final ! i | i <- [512..ub]]
    denom = foldl' {-'-} mulm 1 as
ub = 1023
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import Data.Array
import Data.Bits
import Data.List

main = do
  n <- readLn
  as <- map read . words <$> getLine
  let ans = abc310f n as
  print ans

type State = Array Int Int -- 作れる数のビット集合 → 場合の数

abc310f :: Int -> [Int] -> Int
abc310f n as = divm answer denom
  where
    initial = accumArray (+) 0 (0,ub) [(0,1)]
    final = foldl' {-'-} step initial as
    answer = foldl' {-'-} addm 0 [final ! i | i <- [512..ub]]
    denom = foldl' {-'-} mulm 1 as

ub = 1023

step :: State -> Int -> State
step m ai = accumArray addm 0 (0,ub) $
  [ (s, mulm cnt (ai - 10)) | ai > 10, (s, cnt) <- assocs m] ++
  [ (bs2ix bs1, cnt)
  | (s, cnt) <- assocs m, let bs = ix2bs s
  , x <- [1 .. min 10 ai]
  , let bs1 = bs .|. (shiftL bs x .&. mask)
  ]

mask = 2047

-- 添え字からビット集合
ix2bs i = shiftL i 1 .|. 1
-- ビット集合から添え字
bs2ix b = shiftR b 1

-- モジュロ演算
modBase = 998244353
reg x = mod x modBase
addm x y = reg (x + y)
mulm x y = reg (x * y)
divm x y = powerish mulm x y (modBase - 2)
powerish mul i a b = foldl' {-'-} mul i [p | (b,p) <- zip bs ps, odd b]
  where
    bs = takeWhile (0 /=) $ iterate (flip shiftR 1) b
    ps = iterate (\x -> mul x x) a

Submission Info

Compile Error

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

Judge Result