import * as fs from 'fs' import { resolve } from 'path' /** * 位集,用于存储大量的布尔值,可以有效地节省内存. * 1e9个元素 => 125MB. */ class BitSet { static from(arrayLike: ArrayLike): 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 = 4 // !理论最优是logn,实际取8效果最好(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)