結果

問題 No.1043 直列大学
ユーザー nadeshinonadeshino
提出日時 2020-05-01 22:20:58
言語 Nim
(2.0.2)
結果
AC  
実行時間 238 ms / 2,000 ms
コード長 3,895 bytes
コンパイル時間 3,065 ms
コンパイル使用メモリ 66,468 KB
実行使用メモリ 84,224 KB
最終ジャッジ日時 2024-06-02 02:55:23
合計ジャッジ時間 9,202 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 91 ms
84,224 KB
testcase_01 AC 89 ms
84,224 KB
testcase_02 AC 96 ms
84,224 KB
testcase_03 AC 89 ms
84,224 KB
testcase_04 AC 89 ms
84,224 KB
testcase_05 AC 87 ms
84,224 KB
testcase_06 AC 91 ms
84,224 KB
testcase_07 AC 93 ms
84,224 KB
testcase_08 AC 93 ms
84,224 KB
testcase_09 AC 161 ms
84,224 KB
testcase_10 AC 175 ms
84,224 KB
testcase_11 AC 220 ms
84,224 KB
testcase_12 AC 238 ms
84,096 KB
testcase_13 AC 215 ms
84,224 KB
testcase_14 AC 217 ms
84,224 KB
testcase_15 AC 234 ms
84,224 KB
testcase_16 AC 212 ms
84,224 KB
testcase_17 AC 183 ms
84,224 KB
testcase_18 AC 188 ms
84,224 KB
testcase_19 AC 212 ms
84,224 KB
testcase_20 AC 179 ms
84,224 KB
testcase_21 AC 197 ms
84,224 KB
testcase_22 AC 206 ms
84,224 KB
testcase_23 AC 231 ms
84,224 KB
testcase_24 AC 186 ms
84,224 KB
testcase_25 AC 211 ms
84,224 KB
testcase_26 AC 231 ms
84,224 KB
testcase_27 AC 153 ms
84,224 KB
testcase_28 AC 206 ms
84,224 KB
testcase_29 AC 123 ms
84,224 KB
testcase_30 AC 177 ms
84,224 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import algorithm, math, sequtils, strutils

let read* = iterator: string =
  while true: (for s in stdin.readLine.split: yield s)

template input*(T: static[typedesc]): untyped = 
  when T is int: read().parseInt
  elif T is float: read().parseFloat
  elif T is string: read()

# -------------------------------------------------- #

template useModInt*(p: static[Positive]) =
  type ModInt* {.inject.} = distinct int

  proc toModInt*(n: int): ModInt {.inline.} =
    if n >= p + p:
      ModInt(n mod p)
    elif n >= p:
      ModInt(n - p)
    elif n >= 0:
      ModInt(n)
    elif n >= -p:
      ModInt(n + p)
    else:
      ModInt((n mod p + p) mod p)

  proc inverse*(n: range[1 .. p - 1]): ModInt {.inline.} =
    var (sx, tx, s, t) = (0, 1, p, n)
    while t != 1:
      let k = s div t
      s -= t * k; swap(s, t)
      sx -= tx * k; swap(sx, tx)
    return toModInt(tx)

  proc inverse*(n: ModInt): ModInt {.inline.} =
    inverse(int(n))
    
  proc `$`*(n: ModInt): string {.borrow.}
  proc `+`*(n: ModInt): ModInt {.borrow.}
  proc `-`*(n: ModInt): ModInt {.inline.} =
    ModInt((p - int(n)) * int(int(n) != 0))

  proc `<`*(n: ModInt, m: ModInt): bool {.borrow.}
  proc `<`*(n: ModInt, m: int): bool {.borrow.}
  proc `<`*(n: int, m: ModInt): bool {.borrow.}
  proc `<=`*(n: ModInt, m: ModInt): bool {.borrow.}
  proc `<=`*(n: ModInt, m: int): bool {.borrow.}
  proc `<=`*(n: int, m: ModInt): bool {.borrow.}
  proc `==`*(n: ModInt, m: ModInt): bool {.borrow.}
  proc `==`*(n: ModInt, m: int): bool {.borrow.}
  proc `==`*(n: int, m: ModInt): bool {.borrow.}
 
  proc `+`*(n: ModInt, m: ModInt): ModInt {.inline.} =
    ModInt(int(n) + int(m) - p * int(int(n) + int(m) >= p))
  proc `+`*(n: ModInt, m: int): ModInt {.inline.} =
    toModInt(int(n) + m)
  proc `+`*(n: int, m: ModInt): ModInt {.inline.} =
    toModInt(n + int(m))
  proc `-`*(n: ModInt, m: ModInt): ModInt {.inline.} =
    ModInt(int(n) - int(m) + p * int(int(n) - int(m) < 0))
  proc `-`*(n: ModInt, m: int): ModInt {.inline.} =
    toModInt(int(n) + m)
  proc `-`*(n: int, m: ModInt): ModInt {.inline.} =
    toModInt(n + int(m))
  proc `*`*(n: ModInt, m: ModInt): ModInt {.inline.} =
    toModInt(int(n) * int(m))
  proc `*`*(n: ModInt, m: int): ModInt {.inline.} =
    toModInt(int(n) * m)
  proc `*`*(n: int, m: ModInt): ModInt {.inline.} =
    toModInt(n * int(m))
  proc `/`*(n: ModInt, m: ModInt): ModInt {.inline.} =
    toModInt(int(n) * int(inverse(m)))
  proc `/`*(n: ModInt, m: int): ModInt {.inline.} =
    toModInt(int(n) * int(inverse(m)))
  proc `/`*(n: int, m: ModInt): ModInt {.inline.} =
    toModInt(n * int(inverse(m)))

  proc `+=`*(n: var ModInt, m: ModInt) {.inline.} =
    n = n + m
  proc `+=`*(n: var ModInt, m: int) {.inline.} =
    n = n + m
  proc `-=`*(n: var ModInt, m: ModInt) {.inline.} =
    n = n - m
  proc `-=`*(n: var ModInt, m: int) {.inline.} =
    n = n - m
  proc `*=`*(n: var ModInt, m: ModInt) {.inline.} =
    n = n * m
  proc `*=`*(n: var ModInt, m: int) {.inline.} =
    n = n * m
  proc `/=`*(n: var ModInt, m: ModInt) {.inline.} =
    n = n / m
  proc `/=`*(n: var ModInt, m: int) {.inline.} =
    n = n / m
    
# -------------------------------------------------- #

useModInt(1000000007)
let N, M = input(int)
let V = @[0] & newSeqWith(N, input(int))
let R = @[0] & newSeqWith(M, input(int))
let A, B = input(int)
proc f(N: int, V: seq[int]): seq[ModInt] =
  var dp: array[0 .. 100, array[0 .. 100000, ModInt]]
  dp[0][0] = ModInt(1)
  for i in 1 .. N:
    for j in 0 .. 100000:
      if j - V[i] >= 0:
        dp[i][j] += dp[i - 1][j - V[i]]
      dp[i][j] += dp[i - 1][j]
  var A = newSeq[ModInt](100001)
  for i in 1 .. 100000:
    A[i] = dp[N][i]
  return A
let P = f(N, V).cumsummed
let Q = f(M, R)
var res = ModInt(0)
for j in 0 .. 100000:
  let R = (j * B).clamp(0, 100000)
  let L = (j * A - 1).clamp(0, 100000)
  res += (P[R] - P[L]) * Q[j]
echo res
0