結果

問題 No.1043 直列大学
ユーザー nadeshino
提出日時 2020-05-01 22:20:58
言語 Nim
(2.2.0)
結果
AC  
実行時間 272 ms / 2,000 ms
コード長 3,895 bytes
コンパイル時間 5,472 ms
コンパイル使用メモリ 66,516 KB
実行使用メモリ 84,352 KB
最終ジャッジ日時 2024-12-22 19:33:10
合計ジャッジ時間 12,086 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

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