結果
| 問題 |
No.1340 おーじ君をさがせ
|
| コンテスト | |
| ユーザー |
 草苺奶昔
|
| 提出日時 | 2023-06-05 20:20:55 |
| 言語 | TypeScript (5.7.2) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 15,100 bytes |
| コンパイル時間 | 8,149 ms |
| コンパイル使用メモリ | 233,660 KB |
| 実行使用メモリ | 45,552 KB |
| 最終ジャッジ日時 | 2024-12-31 16:50:32 |
| 合計ジャッジ時間 | 13,857 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | RE * 3 |
| other | RE * 59 |
ソースコード
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('')
}
private _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
}
private _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
}
private _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
}
private _onesCount(): number {
let count = 0
for (let i = 0; i < this._bits.length; i++) {
count += BitSet._onesCount32(this._bits[i])
}
return count
}
/**
* hack.
* ![start,end) 范围内数与bitset相交的数.end-start<32.
* @example
* [start,end) = [10,16)
* [15,14,13,12,11,10] & Bitset(10,11,13,15) => 101011
*/
_hasRange(start: number, end: number): number {
const posL = start >> 5
const shiftL = start & 31
const posR = end >> 5
const shiftR = end & 31
const maskL = ~(~0 << shiftL)
const maskR = ~(~0 << shiftR)
if (posL === posR) return (this._bits[posL] & maskR) >>> shiftL
return ((this._bits[posL] & ~maskL) >>> shiftL) | ((this._bits[posR] & maskR) << (32 - shiftL))
}
}
/**
* 布尔方阵.单次矩阵乘法的复杂度为 `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)
}
/**
* 稠密矩阵,5000*5000 => 800ms.
*/
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 = 7 // !理论最优是logn,实际取7效果最好(n为5000时)
this._initDpIfAbsent(step, n)
const dp = this._dp!
const otherBs = other._bs
const trailingZeros32 = BooleanSquareMatrixDense._trailingZeros32
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 = 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; i < n; i++) {
const now = this._bs[i]._hasRange(left, right)
res._bs[i].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`.
* 稠密矩阵,2000*2000 => 1.4s.
*/
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('./a.txt')
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)
}
console.log(mat.print())
mat.ipow(t)
let res = 0
for (let i = 0; i < n; i++) res += +mat.get(0, i)
console.log(res)