結果

問題 No.1340 おーじ君をさがせ
コンテスト
ユーザー 草苺奶昔
提出日時 2023-06-05 12:03:46
言語 Go
(1.23.4)
結果
AC  
実行時間 16 ms / 2,000 ms
コード長 5,361 bytes
コンパイル時間 15,688 ms
コンパイル使用メモリ 233,184 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-29 05:59:45
合計ジャッジ時間 13,266 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 59
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import (
	"bufio"
	"fmt"
	"math/bits"
	"math/rand"
	"os"
	"strings"
	"time"
)

func main() {
	yuki1340()
	// demo()
}

// https://yukicoder.me/problems/no/1340
// 给定一个n个点m条边的有向图，求t步后可能所在的顶点个数(每一步必须移动到一个相邻点).
// n<=100 m<=1e4 t<=1e18
func yuki1340() {

	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n, m, t int
	fmt.Fscan(in, &n, &m, &t)
	mat := NewBooleanMatrix(n, n)
	for i := 0; i < m; i++ {
		var a, b int
		fmt.Fscan(in, &a, &b)
		mat.Set(a, b, true)
	}
	mat.IPow(t)
	res := 0
	for i := 0; i < n; i++ {
		if mat.Get(0, i) {
			res++
		}
	}
	fmt.Fprintln(out, res)
}

// https://leetcode.cn/problems/course-schedule-iv/
func checkIfPrerequisite(numCourses int, prerequisites [][]int, queries [][]int) []bool {
	mat := NewBooleanMatrix(numCourses, numCourses)
	for _, p := range prerequisites {
		mat.Set(p[0], p[1], true)
	}
	trans := mat.TransitiveClosure()
	res := make([]bool, len(queries))
	for i, q := range queries {
		res[i] = trans.Get(q[0], q[1])
	}
	return res
}

func demo() {
	mat := NewBooleanMatrix(3, 3)
	mat.Set(0, 0, true)
	mat.Set(0, 1, true)
	mat.Set(1, 2, true)
	mat.Set(1, 0, true)

	// 5000*5000的矩阵乘法 => 836ms
	N_5000 := 5000
	eye := Eye(N_5000)
	for i := 0; i < N_5000; i++ {
		for j := 0; j < N_5000; j++ {
			if rand.Intn(2) == 0 {
				eye.Set(i, j, true)
			}
		}
	}
	time1 := time.Now()
	Mul(eye, eye)
	time2 := time.Now()
	fmt.Println(time2.Sub(time1))

	// 2000*2000的传递闭包 => 1.26s
	N_2000 := 2000
	eye = Eye(N_2000)
	for i := 0; i < N_2000; i++ {
		for j := 0; j < N_2000; j++ {
			if rand.Intn(2) == 0 {
				eye.Set(i, j, true)
			}
		}
	}

	time3 := time.Now()
	eye.TransitiveClosure()
	time4 := time.Now()
	fmt.Println(time4.Sub(time3))
}

type BooleanMatrix struct {
	ROW, COL int
	bs       []Bitset
}

func NewBooleanMatrix(row, col int) *BooleanMatrix {
	bs := make([]Bitset, row)
	for i := range bs {
		bs[i] = NewBitset(col)
	}
	return &BooleanMatrix{ROW: row, COL: col, bs: bs}
}

func Eye(n int) *BooleanMatrix {
	res := NewBooleanMatrix(n, n)
	for i := 0; i < n; i++ {
		res.bs[i].Set(i)
	}
	return res
}

func Pow(mat *BooleanMatrix, k int) *BooleanMatrix {
	return mat.Copy().IPow(k)
}

func Mul(mat1, mat2 *BooleanMatrix) *BooleanMatrix {
	return mat1.Copy().IMul(mat2)
}

func Add(mat1, mat2 *BooleanMatrix) *BooleanMatrix {
	return mat1.Copy().IAdd(mat2)
}

// (A + I)^n 是传递闭包.
func (bm *BooleanMatrix) TransitiveClosure() *BooleanMatrix {
	n := bm.ROW
	newMat := Add(bm, Eye(n))
	newMat.IPow(n)
	return newMat
}

func (bm *BooleanMatrix) IPow(k int) *BooleanMatrix {
	res := Eye(bm.ROW)
	for k > 0 {
		if k&1 == 1 {
			res.IMul(bm)
		}
		bm.IMul(bm)
		k >>= 1
	}
	res.bs, bm.bs = bm.bs, res.bs
	return bm
}

// square matrix
func (bm *BooleanMatrix) IMul(mat *BooleanMatrix) *BooleanMatrix {
	n := mat.ROW
	res := NewBooleanMatrix(n, n)
	step := 1
	dp := make([]Bitset, 1<<step)
	for i := range dp {
		dp[i] = NewBitset(n)
	}

	for l, r := 0, step; l != n; {
		if r > n {
			r = n
		}
		for s := 1; s != (1 << step); s++ {
			lb := bits.TrailingZeros(uint(s))
			dp[s] = Or(dp[s^(1<<lb)], mat.bs[l+lb])
		}
		for i, now := 0, 0; i != n; {
			for j := l; j != r; j++ {
				if bm.bs[i].Has(j) {
					now ^= 1 << (j - l)
				}
			}
			res.bs[i].IOr(dp[now]) // find in table
			i++
			now = 0
		}
		l = r
		r += step
	}

	bm.bs, res.bs = res.bs, bm.bs
	return res
}

func (bm *BooleanMatrix) IAdd(mat *BooleanMatrix) *BooleanMatrix {
	for i := 0; i < bm.ROW; i++ {
		bm.bs[i].IOr(mat.bs[i])
	}
	return bm
}

func (bm *BooleanMatrix) Copy() *BooleanMatrix {
	bs := make([]Bitset, bm.ROW)
	for i := range bs {
		bs[i] = bm.bs[i].Copy()
	}
	return &BooleanMatrix{ROW: bm.ROW, COL: bm.COL, bs: bs}
}

func (bm *BooleanMatrix) Get(row, col int) bool {
	return bm.bs[row].Has(col)
}

func (bm *BooleanMatrix) Set(row, col int, b bool) {
	if b {
		bm.bs[row].Set(col)
	} else {
		bm.bs[row].Reset(col)
	}
}

// To 2D grid.
func (mat *BooleanMatrix) String() string {
	grid := make([][]int, mat.ROW)
	for i := 0; i < mat.ROW; i++ {
		grid[i] = make([]int, mat.COL)
		for j := 0; j < mat.COL; j++ {
			if mat.Get(i, j) {
				grid[i][j] = 1
			} else {
				grid[i][j] = 0
			}
		}
	}

	sb := strings.Builder{}
	sb.WriteString(fmt.Sprintf("BooleanMatrix(%d,%d)\n", mat.ROW, mat.COL))
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[0]); j++ {
			sb.WriteString(fmt.Sprintf("%d ", grid[i][j]))
		}
		sb.WriteString("\n")
	}

	return sb.String()
}

const _w = bits.UintSize

type Bitset []uint

func NewBitset(n int) Bitset { return make(Bitset, n/_w+1) } // (n+_w-1)/_w

func (b Bitset) Has(p int) bool { return b[p/_w]&(1<<(p%_w)) != 0 }
func (b Bitset) Flip(p int)     { b[p/_w] ^= 1 << (p % _w) }
func (b Bitset) Set(p int)      { b[p/_w] |= 1 << (p % _w) }
func (b Bitset) Reset(p int)    { b[p/_w] &^= 1 << (p % _w) }

func (b Bitset) Copy() Bitset {
	res := make(Bitset, len(b))
	copy(res, b)
	return res
}

func Or(a, b Bitset) Bitset {
	res := make(Bitset, len(a))
	for i, v := range a {
		res[i] = v | b[i]
	}
	return res
}

// 将 c 的元素合并进 b
func (b Bitset) IOr(c Bitset) Bitset {
	for i, v := range c {
		b[i] |= v
	}
	return b
}

// !f2上的加法
func (b Bitset) IXOr(c Bitset) {
	for i, v := range c {
		b[i] ^= v
	}
}
0