結果

問題 No.1340 おーじ君をさがせ
コンテスト
ユーザー 草苺奶昔
提出日時 2023-06-04 20:10:04
言語 Go
(1.23.4)
結果
RE  
実行時間 -
コード長 4,221 bytes
コンパイル時間 15,424 ms
コンパイル使用メモリ 230,112 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-29 03:47:35
合計ジャッジ時間 12,895 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 31 WA * 17 RE * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import (
	"bufio"
	"fmt"
	"os"
	"strings"
	"time"
)

func main() {
	yuki1340()
}

// https://yukicoder.me/problems/no/1340
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 = Pow(mat, t)
	res := 0
	for i := 0; i < n; i++ {
		if mat.Get(0, i) {
			res++
		}
	}
	fmt.Fprintln(out, 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)
	fmt.Println(mat)
	fmt.Println(Transpose(mat))
	fmt.Println(Mul(Mul(mat, mat), mat), Pow(mat, 3))
	fmt.Println(Eye(8))

	// 5000*5000的矩阵乘法 => 643.2133ms
	time1 := time.Now()
	eye := Eye(5000)
	Mul(eye, eye)
	time2 := time.Now()
	fmt.Println(time2.Sub(time1))

	// 2000*2000的传递闭包 => 620.574ms
	time3 := time.Now()
	n := 2000
	newEye := Eye(n)
	TransitiveClosure(newEye)
	time4 := time.Now()
	fmt.Println(time4.Sub(time3))
}

func NewBooleanMatrix(row, col int) *BooleanMatrix {
	return &BooleanMatrix{ROW: row, COL: col, x: make([]uint64, (1+row>>3)*(1+col>>3))}
}

func Eye(n int) *BooleanMatrix {
	res := NewBooleanMatrix(n, n)
	size := 1 + n>>3
	for i := 0; i < size; i++ {
		res.x[i*size+i] = 0x8040201008040201
	}
	return res
}

// 返回一个新的矩阵,值为mat1*mat2.
func Mul(mat1, mat2 *BooleanMatrix) *BooleanMatrix {
	r1, c1, r2, c2 := 1+mat1.ROW>>3, 1+mat1.COL>>3, 1+mat2.ROW>>3, 1+mat2.COL>>3
	res := NewBooleanMatrix(mat1.ROW, mat2.COL)
	for i := 0; i < r1; i++ {
		for k := 0; k < r2; k++ {
			for j := 0; j < c2; j++ {
				res.x[i*c2+j] |= _mul(mat1.x[i*c1+k], mat2.x[k*c2+j])
			}
		}
	}
	return res
}

// 求方阵mat的k次幂.
func Pow(mat *BooleanMatrix, k int) *BooleanMatrix {
	res := Eye(mat.ROW)
	for ; k > 0; k >>= 1 {
		if k&1 != 0 {
			res = Mul(res, mat)
		}
		mat = Mul(mat, mat)
	}
	return res
}

func Transpose(mat *BooleanMatrix) *BooleanMatrix {
	row, col := 1+mat.ROW>>3, 1+mat.COL>>3
	res := NewBooleanMatrix(mat.COL, mat.ROW)
	for i := 0; i < row; i++ {
		for j := 0; j < col; j++ {
			res.x[j*row+i] = _transpose(mat.x[i*col+j])
		}
	}
	return res
}

// 返回一个新的矩阵,值为mat1|mat2.
func Add(mat1, mat2 *BooleanMatrix) *BooleanMatrix {
	res := mat1.Copy()
	row, col := 1+mat1.ROW>>3, 1+mat1.COL>>3
	for i := 0; i < row; i++ {
		for j := 0; j < col; j++ {
			pos := i*col + j
			res.x[pos] |= mat2.x[pos]
		}
	}
	return res
}

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

//
//
type BooleanMatrix struct {
	ROW, COL int
	x        []uint64
}

func (mat *BooleanMatrix) Get(i, j int) bool {
	return mat.x[(i>>3)<<3|j>>3]&(1<<((i&7)<<3|j&7)) != 0 // % 8 => & 7
}

func (mat *BooleanMatrix) Set(i, j int, b bool) {
	if b {
		mat.x[(i>>3)<<3|j>>3] |= (1 << ((i&7)<<3 | j&7))
	} else {
		mat.x[(i>>3)<<3|j>>3] &= ^(1 << ((i&7)<<3 | j&7))
	}
}

func (mat *BooleanMatrix) Copy() *BooleanMatrix {
	return &BooleanMatrix{ROW: mat.ROW, COL: mat.COL, x: append(mat.x[:0:0], mat.x...)}
}

// 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()
}

// C[i][j] |= A[i][k] & B[k][j]
func _mul(a, b uint64) uint64 {
	u := uint64(0xff)
	v := uint64(0x101010101010101)
	c := uint64(0)
	for a != 0 && b != 0 {
		c |= (((a & v) * u) & ((b & u) * v))
		a >>= 1
		b >>= 8
	}
	return c
}

func _transpose(a uint64) uint64 {
	t := (a ^ (a >> 7)) & 0x00aa00aa00aa00aa
	a = a ^ t ^ (t << 7)
	t = (a ^ (a >> 14)) & 0x0000cccc0000cccc
	a = a ^ t ^ (t << 14)
	t = (a ^ (a >> 28)) & 0x00000000f0f0f0f0
	a = a ^ t ^ (t << 28)
	return a
}
0