結果

問題 No.1340 おーじ君をさがせ
ユーザー 草苺奶昔草苺奶昔
提出日時 2023-06-05 16:07:28
言語 TypeScript
(5.7.2)
結果
AC  
実行時間 187 ms / 2,000 ms
コード長 14,512 bytes
コンパイル時間 8,491 ms
コンパイル使用メモリ 234,096 KB
実行使用メモリ 50,736 KB
最終ジャッジ日時 2024-12-31 16:50:29
合計ジャッジ時間 17,660 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 77 ms
44,032 KB
testcase_01 AC 76 ms
44,032 KB
testcase_02 AC 78 ms
43,904 KB
testcase_03 AC 78 ms
44,160 KB
testcase_04 AC 77 ms
44,032 KB
testcase_05 AC 76 ms
44,032 KB
testcase_06 AC 76 ms
43,904 KB
testcase_07 AC 78 ms
44,032 KB
testcase_08 AC 75 ms
43,776 KB
testcase_09 AC 76 ms
43,776 KB
testcase_10 AC 104 ms
47,232 KB
testcase_11 AC 122 ms
47,692 KB
testcase_12 AC 113 ms
47,680 KB
testcase_13 AC 120 ms
47,188 KB
testcase_14 AC 128 ms
48,712 KB
testcase_15 AC 141 ms
48,748 KB
testcase_16 AC 106 ms
46,592 KB
testcase_17 AC 119 ms
47,812 KB
testcase_18 AC 141 ms
48,608 KB
testcase_19 AC 107 ms
47,488 KB
testcase_20 AC 105 ms
47,616 KB
testcase_21 AC 164 ms
49,896 KB
testcase_22 AC 166 ms
50,056 KB
testcase_23 AC 165 ms
49,956 KB
testcase_24 AC 168 ms
49,344 KB
testcase_25 AC 128 ms
48,892 KB
testcase_26 AC 121 ms
47,828 KB
testcase_27 AC 116 ms
47,744 KB
testcase_28 AC 128 ms
49,088 KB
testcase_29 AC 116 ms
47,488 KB
testcase_30 AC 146 ms
48,924 KB
testcase_31 AC 181 ms
50,736 KB
testcase_32 AC 183 ms
50,604 KB
testcase_33 AC 184 ms
50,732 KB
testcase_34 AC 179 ms
50,732 KB
testcase_35 AC 187 ms
50,728 KB
testcase_36 AC 83 ms
45,440 KB
testcase_37 AC 106 ms
47,872 KB
testcase_38 AC 185 ms
50,640 KB
testcase_39 AC 143 ms
50,092 KB
testcase_40 AC 141 ms
49,964 KB
testcase_41 AC 139 ms
49,840 KB
testcase_42 AC 76 ms
44,160 KB
testcase_43 AC 76 ms
44,032 KB
testcase_44 AC 88 ms
46,208 KB
testcase_45 AC 84 ms
44,928 KB
testcase_46 AC 122 ms
47,052 KB
testcase_47 AC 122 ms
47,052 KB
testcase_48 AC 126 ms
47,464 KB
testcase_49 AC 119 ms
46,804 KB
testcase_50 AC 118 ms
46,936 KB
testcase_51 AC 120 ms
46,680 KB
testcase_52 AC 128 ms
48,896 KB
testcase_53 AC 130 ms
48,732 KB
testcase_54 AC 129 ms
48,772 KB
testcase_55 AC 142 ms
49,064 KB
testcase_56 AC 83 ms
45,440 KB
testcase_57 AC 83 ms
45,312 KB
testcase_58 AC 84 ms
44,800 KB
testcase_59 AC 116 ms
46,644 KB
testcase_60 AC 74 ms
43,776 KB
testcase_61 AC 114 ms
46,820 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import * as fs from 'fs'
import { resolve } from 'path'

/**
 * 位集,用于存储大量的布尔值,可以有效地节省内存.
 * 1e9个元素 => 125MB.
 */
class BitSet {
  static from(arrayLike: ArrayLike<number | string>): BitSet {
    const bitSet = new BitSet(arrayLike.length)
    for (let i = 0; i < arrayLike.length; i++) {
      if (Number(arrayLike[i]) === 1) {
        bitSet.add(i)
      }
    }
    return bitSet
  }

  // lowbit.bit_length() - 1
  private static _trailingZeros32(uint32: number): number {
    if (uint32 === 0) return 32
    return 31 - Math.clz32(uint32 & -uint32) // bitLength32(uint32 & -uint32) - 1
  }
  private static _onesCount32(uint32: number): number {
    uint32 -= (uint32 >>> 1) & 0x55555555
    uint32 = (uint32 & 0x33333333) + ((uint32 >>> 2) & 0x33333333)
    return (((uint32 + (uint32 >>> 4)) & 0x0f0f0f0f) * 0x01010101) >>> 24
  }
  private static _bitLength32(uint32: number): number {
    return 32 - Math.clz32(uint32)
  }

  private readonly _bits: Uint32Array
  private readonly _n: number

  constructor(n: number) {
    this._bits = new Uint32Array((n >> 5) + 1)
    this._n = n
  }

  add(i: number): void {
    this._bits[i >> 5] |= 1 << (i & 31)
  }

  /**
   * [start, end) 范围内的位置为 1
   */
  addRange(start: number, end: number): void {
    const maskL = ~0 << (start & 31)
    const maskR = ~0 << (end & 31)
    let i = start >> 5
    if (i === end >> 5) {
      this._bits[i] |= maskL ^ maskR
      return
    }
    this._bits[i] |= maskL
    for (i++; i < end >> 5; i++) {
      this._bits[i] = ~0
    }
    this._bits[i] |= ~maskR
  }

  has(i: number): boolean {
    return !!(this._bits[i >> 5] & (1 << (i & 31)))
  }

  discard(i: number): void {
    this._bits[i >> 5] &= ~(1 << (i & 31))
  }

  /**
   * [start, end) 范围内的位置为 0
   */
  discardRange(start: number, end: number): void {
    const maskL = ~0 << (start & 31)
    const maskR = ~0 << (end & 31)
    let i = start >> 5
    if (i === end >> 5) {
      this._bits[i] &= ~maskL | maskR
      return
    }
    this._bits[i] &= ~maskL
    for (i++; i < end >> 5; i++) {
      this._bits[i] = 0
    }
    this._bits[i] &= maskR
  }

  flip(i: number): void {
    this._bits[i >> 5] ^= 1 << (i & 31)
  }

  /**
   * [start, end) 范围内的位取反
   */
  flipRange(start: number, end: number): void {
    const maskL = ~0 << (start & 31)
    const maskR = ~0 << (end & 31)
    let i = start >> 5
    if (i === end >> 5) {
      this._bits[i] ^= maskL ^ maskR
      return
    }
    this._bits[i] ^= maskL
    for (i++; i < end >> 5; i++) {
      this._bits[i] = ~this._bits[i]
    }
    this._bits[i] ^= ~maskR
  }

  clear(): void {
    this._bits.fill(0)
  }

  /**
   * [start, end) 范围内是否全为 1
   */
  allOne(start: number, end: number): boolean {
    let i = start >> 5
    if (i === end >> 5) {
      const mask = (~0 << (start & 31)) ^ (~0 << (end & 31))
      return (this._bits[i] & mask) === mask
    }
    let mask = ~0 << (start & 31)
    if ((this._bits[i] & mask) !== mask) {
      return false
    }
    for (i++; i < end >> 5; i++) {
      if (~this._bits[i]) {
        return false
      }
    }
    mask = ~0 << (end & 31)
    return !~(this._bits[end >> 5] | mask)
  }

  /**
   * [start, end) 范围内是否全为 0
   */
  allZero(start: number, end: number): boolean {
    let i = start >> 5
    if (i === end >> 5) {
      const mask = (~0 << (start & 31)) ^ (~0 << (end & 31))
      return !(this._bits[i] & mask)
    }
    if (this._bits[i] >> (start & 31)) {
      return false
    }
    for (i++; i < end >> 5; i++) {
      if (this._bits[i]) {
        return false
      }
    }
    const mask = ~0 << (end & 31)
    return !(this._bits[end >> 5] & ~mask)
  }

  /**
   * 返回第一个 0 的下标，若不存在则返回-1
   * @param position 从哪个位置开始查找
   */
  indexOfZero(position = 0): number {
    if (position === 0) {
      return this._indexOfZero()
    }

    let i = position >> 5
    if (i < this._bits.length) {
      let v = this._bits[i]
      if (position & 31) {
        v |= ~(~0 << (position & 31))
      }
      if (~v) {
        const res = (i << 5) | BitSet._trailingZeros32(~v)
        return res < this._n ? res : -1
      }
      for (i++; i < this._bits.length; i++) {
        if (~this._bits[i]) {
          const res = (i << 5) | BitSet._trailingZeros32(~this._bits[i])
          return res < this._n ? res : -1
        }
      }
    }

    return -1
  }

  /**
   * 返回第一个 1 的下标，若不存在则返回-1
   * @param position 从哪个位置开始查找
   */
  indexOfOne(position = 0): number {
    if (!position) {
      return this._indexOfOne()
    }

    // eslint-disable-next-line space-in-parens
    for (let i = position >> 5; i < this._bits.length; ) {
      const v = this._bits[i] & (~0 << (position & 31))
      if (v) {
        return (i << 5) | BitSet._trailingZeros32(v)
      }
      for (i++; i < this._bits.length; i++) {
        if (this._bits[i]) {
          return (i << 5) | BitSet._trailingZeros32(this._bits[i])
        }
      }
    }

    return -1
  }

  /**
   * 返回 [start, end) 范围内 1 的个数
   */
  onesCount(start = 0, end = this._n): number {
    if (start < 0) {
      start = 0
    }
    if (end > this._n) {
      end = this._n
    }
    if (!start && end === this._n) {
      return this._onesCount()
    }

    let pos1 = start >> 5
    const pos2 = end >> 5
    if (pos1 === pos2) {
      return BitSet._onesCount32(this._bits[pos1] & (~0 << (start & 31)) & ((1 << (end & 31)) - 1))
    }

    let count = 0
    if ((start & 31) > 0) {
      count += BitSet._onesCount32(this._bits[pos1] & (~0 << (start & 31)))
      pos1++
    }
    for (let i = pos1; i < pos2; i++) {
      count += BitSet._onesCount32(this._bits[i])
    }
    if ((end & 31) > 0) {
      count += BitSet._onesCount32(this._bits[pos2] & ((1 << (end & 31)) - 1))
    }
    return count
  }

  equals(other: BitSet): boolean {
    if (this._bits.length !== other._bits.length) {
      return false
    }
    for (let i = 0; i < this._bits.length; i++) {
      if (this._bits[i] !== other._bits[i]) {
        return false
      }
    }
    return true
  }

  isSubset(other: BitSet): boolean {
    if (this._bits.length > other._bits.length) {
      return false
    }
    for (let i = 0; i < this._bits.length; i++) {
      if ((this._bits[i] & other._bits[i]) >>> 0 !== this._bits[i]) {
        return false
      }
    }
    return true
  }

  isSuperset(other: BitSet): boolean {
    if (this._bits.length < other._bits.length) {
      return false
    }
    for (let i = 0; i < other._bits.length; i++) {
      if ((this._bits[i] & other._bits[i]) >>> 0 !== other._bits[i]) {
        return false
      }
    }
    return true
  }

  ior(other: BitSet): BitSet {
    for (let i = 0; i < this._bits.length; i++) {
      this._bits[i] |= other._bits[i]
    }
    return this
  }

  or(other: BitSet): BitSet {
    const res = new BitSet(this._n)
    for (let i = 0; i < this._bits.length; i++) {
      res._bits[i] = this._bits[i] | other._bits[i]
    }
    return res
  }

  iand(other: BitSet): BitSet {
    for (let i = 0; i < this._bits.length; i++) {
      this._bits[i] &= other._bits[i]
    }
    return this
  }

  and(other: BitSet): BitSet {
    const res = new BitSet(this._n)
    for (let i = 0; i < this._bits.length; i++) {
      res._bits[i] = this._bits[i] & other._bits[i]
    }
    return res
  }

  ixor(other: BitSet): BitSet {
    for (let i = 0; i < this._bits.length; i++) {
      this._bits[i] ^= other._bits[i]
    }
    return this
  }

  xor(other: BitSet): BitSet {
    const res = new BitSet(this._n)
    for (let i = 0; i < this._bits.length; i++) {
      res._bits[i] = this._bits[i] ^ other._bits[i]
    }
    return res
  }

  copy(): BitSet {
    const res = new BitSet(this._n)
    res._bits.set(this._bits)
    return res
  }

  bitLength(): number {
    return this._lastIndexOfOne() + 1
  }

  toString(): string {
    const sb: string[] = []
    for (let i = 0; i < this._bits.length; i++) {
      // eslint-disable-next-line newline-per-chained-call
      let bits = this._bits[i].toString(2).padStart(32, '0').split('').reverse().join('')
      if (i === this._bits.length - 1) {
        bits = bits.slice(0, this._n & 31)
      }
      sb.push(bits)
    }
    return sb.join('')
  }

  _indexOfZero(): number {
    for (let i = 0; i < this._bits.length; i++) {
      const x = this._bits[i]
      if (~x) {
        return (i << 5) | BitSet._trailingZeros32(~x)
      }
    }
    return -1
  }

  _indexOfOne(): number {
    for (let i = 0; i < this._bits.length; i++) {
      const x = this._bits[i]
      if (x) {
        return (i << 5) | BitSet._trailingZeros32(x)
      }
    }
    return -1
  }

  _lastIndexOfOne(): number {
    for (let i = this._bits.length - 1; i >= 0; i--) {
      const x = this._bits[i]
      if (x) {
        return (i << 5) | (BitSet._bitLength32(x) - 1)
      }
    }
    return -1
  }

  _onesCount(): number {
    let count = 0
    for (let i = 0; i < this._bits.length; i++) {
      count += BitSet._onesCount32(this._bits[i])
    }
    return count
  }
}

/**
 * 布尔方针.单次矩阵乘法的复杂度为 `O(n^3/32logn)`.这里的logn为分块的大小.
 * 适用于输入矩阵稠密的情形.
 */
class BooleanSquareMatrixDense {
  static eye(n: number): BooleanSquareMatrixDense {
    const res = new BooleanSquareMatrixDense(n)
    for (let i = 0; i < n; i++) res._bs[i].add(i)
    return res
  }

  static pow(mat: BooleanSquareMatrixDense, k: number): BooleanSquareMatrixDense {
    return mat.copy().ipow(k)
  }

  /**
   * 随机矩阵,4000*4000 => 1.26s.
   */
  static mul(
    mat1: BooleanSquareMatrixDense,
    mat2: BooleanSquareMatrixDense
  ): BooleanSquareMatrixDense {
    return mat1.copy().imul(mat2)
  }

  static add(
    mat1: BooleanSquareMatrixDense,
    mat2: BooleanSquareMatrixDense
  ): BooleanSquareMatrixDense {
    return mat1.copy().iadd(mat2)
  }

  private static _trailingZeros32 = BooleanSquareMatrixDense._initTrailingZeros32()

  private static _initTrailingZeros32(n = 1e4 + 10): Uint8Array {
    const res = new Uint8Array(n + 1)
    res[0] = 32
    for (let i = 1; i < res.length; i++) res[i] = 31 - Math.clz32(i & -i)
    return res
  }

  readonly n: number
  private _bs: BitSet[]
  private _dp?: BitSet[] // 在计算矩阵乘法时用到

  /**
   * @param n n<=1e4.
   */
  constructor(n: number, bs?: BitSet[], dp?: BitSet[]) {
    if (n > 1e4) throw new Error('n should be less than 1e4')
    if (bs === void 0) {
      bs = Array(n)
      for (let i = 0; i < n; i++) bs[i] = new BitSet(n)
    }
    this.n = n
    this._bs = bs
    this._dp = dp
  }

  ipow(k: number): BooleanSquareMatrixDense {
    const res = BooleanSquareMatrixDense.eye(this.n)
    while (k > 0) {
      if (k & 1) res.imul(this)
      this.imul(this)
      k = Math.floor(k / 2) // !注意不能用 `k >>>= 1`, k可能超过uint32
    }
    const tmp = this._bs
    this._bs = res._bs
    res._bs = tmp
    return res
  }

  imul(other: BooleanSquareMatrixDense): BooleanSquareMatrixDense {
    const n = this.n
    const res = new BooleanSquareMatrixDense(n)
    const step = 6 // !理论最优是logn,实际取6效果最好(n为5000时)
    this._initDpIfAbsent(step, n)
    const dp = this._dp!
    const otherBs = other._bs

    for (let left = 0, right = step; left < n; left = right, right += step) {
      if (right > n) right = n
      for (let state = 1; state < 1 << step; state++) {
        const bsf = BooleanSquareMatrixDense._trailingZeros32[state]
        if (left + bsf < n) {
          dp[state] = dp[state ^ (1 << bsf)].or(otherBs[left + bsf]) // !Xor => f2矩阵乘法
        } else {
          dp[state] = dp[state ^ (1 << bsf)]
        }
      }
      for (let i = 0, now = 0; i < n; i++, now = 0) {
        const thisBsI = this._bs[i]
        const resBsI = res._bs[i]
        for (let j = left; j < right; j++) now ^= +thisBsI.has(j) << (j - left)
        resBsI.ior(dp[now]) // !IXor => f2矩阵乘法
      }
    }

    const tmp = this._bs
    this._bs = res._bs
    res._bs = tmp
    return res
  }

  iadd(mat: BooleanSquareMatrixDense): BooleanSquareMatrixDense {
    for (let i = 0; i < this.n; i++) this._bs[i].ior(mat._bs[i])
    return this
  }

  /**
   * 求出邻接矩阵`mat`的传递闭包`(mat+I)^n`.
   * 随机矩阵,1000*1000 => 600ms.
   */
  transitiveClosure(): BooleanSquareMatrixDense {
    const n = this.n
    const trans = BooleanSquareMatrixDense.eye(n).iadd(this)
    trans.ipow(n)
    return trans
  }

  copy(): BooleanSquareMatrixDense {
    const newBs = Array(this.n)
    for (let i = 0; i < this.n; i++) newBs[i] = this._bs[i].copy()
    return new BooleanSquareMatrixDense(this.n, newBs, this._dp)
  }

  get(row: number, col: number): boolean {
    return this._bs[row].has(col)
  }

  set(row: number, col: number, b: boolean): void {
    if (b) {
      this._bs[row].add(col)
    } else {
      this._bs[row].discard(col)
    }
  }

  print(): void {
    const grid: Uint8Array[] = Array(this.n)
    for (let i = 0; i < this.n; i++) {
      grid[i] = new Uint8Array(this.n)
      for (let j = 0; j < this.n; j++) {
        grid[i][j] = this.get(i, j) ? 1 : 0
      }
    }
    // eslint-disable-next-line no-console
    console.table(grid)
  }

  private _initDpIfAbsent(step: number, n: number): void {
    if (this._dp) return
    const dp = Array(1 << step)
    for (let i = 0; i < dp.length; i++) dp[i] = new BitSet(n)
    this._dp = dp
  }
}

function useInput(path?: string) {
  let data: string
  if (path) {
    data = fs.readFileSync(resolve(__dirname, path), 'utf8')
  } else {
    data = fs.readFileSync(process.stdin.fd, 'utf8')
  }

  const lines = data.split(/\r\n|\r|\n/)
  let lineId = 0
  const input = (): string => lines[lineId++]

  return {
    input
  }
}

// https://yukicoder.me/problems/no/1340
// 给定一个n个点m条边的有向图，求t步后可能所在的顶点个数(每一步必须移动到一个相邻点).
// 类似于`无向图中两点间是否存在长度为k的路径`.
// n<=100 m<=1e4 t<=1e18

const { input } = useInput()
const [n, m, t] = input().split(' ').map(Number)

const mat = new BooleanSquareMatrixDense(n)
for (let i = 0; i < m; i++) {
  const [a, b] = input().split(' ').map(Number)
  mat.set(a, b, true)
}

mat.ipow(t)

let res = 0
for (let i = 0; i < n; i++) res += +mat.get(0, i)
console.log(res)
0