結果

問題 No.1043 直列大学
ユーザー nadeshinonadeshino
提出日時 2020-05-01 22:20:58
言語 Nim
(2.0.2)
結果
AC  
実行時間 205 ms / 2,000 ms
コード長 3,895 bytes
コンパイル時間 5,043 ms
コンパイル使用メモリ 72,656 KB
実行使用メモリ 86,012 KB
最終ジャッジ日時 2023-08-24 05:47:43
合計ジャッジ時間 10,252 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
85,800 KB
testcase_01 AC 40 ms
85,840 KB
testcase_02 AC 46 ms
85,852 KB
testcase_03 AC 39 ms
85,836 KB
testcase_04 AC 40 ms
85,984 KB
testcase_05 AC 41 ms
85,844 KB
testcase_06 AC 39 ms
85,848 KB
testcase_07 AC 43 ms
85,984 KB
testcase_08 AC 45 ms
85,800 KB
testcase_09 AC 121 ms
86,008 KB
testcase_10 AC 139 ms
85,860 KB
testcase_11 AC 191 ms
85,836 KB
testcase_12 AC 205 ms
85,960 KB
testcase_13 AC 176 ms
85,828 KB
testcase_14 AC 184 ms
85,856 KB
testcase_15 AC 199 ms
85,872 KB
testcase_16 AC 186 ms
85,888 KB
testcase_17 AC 143 ms
86,012 KB
testcase_18 AC 143 ms
85,816 KB
testcase_19 AC 175 ms
85,820 KB
testcase_20 AC 141 ms
86,000 KB
testcase_21 AC 162 ms
85,876 KB
testcase_22 AC 168 ms
85,876 KB
testcase_23 AC 204 ms
85,892 KB
testcase_24 AC 153 ms
86,008 KB
testcase_25 AC 176 ms
85,964 KB
testcase_26 AC 187 ms
85,900 KB
testcase_27 AC 108 ms
85,936 KB
testcase_28 AC 174 ms
85,828 KB
testcase_29 AC 79 ms
85,960 KB
testcase_30 AC 140 ms
85,848 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