#878129 (Go) No.1340 おーじ君をさがせ

提出ソース

結果

問題	No.1340 おーじ君をさがせ
ユーザー	草苺奶昔
提出日時	2023-06-04 23:04:49
言語	Go (1.22.1)
結果	AC
実行時間	10 ms / 2,000 ms
コード長	4,603 bytes
コンパイル時間	12,247 ms
コンパイル使用メモリ	235,812 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-06-09 04:12:51
合計ジャッジ時間	13,578 ms
ジャッジサーバーID （参考情報）	judge2 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,816 KB
testcase_01	AC	1 ms 6,816 KB
testcase_02	AC	1 ms 6,812 KB
testcase_03	AC	1 ms 6,944 KB
testcase_04	AC	1 ms 6,944 KB
testcase_05	AC	0 ms 6,944 KB
testcase_06	AC	1 ms 6,940 KB
testcase_07	AC	1 ms 6,944 KB
testcase_08	AC	1 ms 6,940 KB
testcase_09	AC	1 ms 6,944 KB
testcase_10	AC	1 ms 6,940 KB
testcase_11	AC	1 ms 6,944 KB
testcase_12	AC	1 ms 6,944 KB
testcase_13	AC	1 ms 6,940 KB
testcase_14	AC	1 ms 6,944 KB
testcase_15	AC	2 ms 6,940 KB
testcase_16	AC	1 ms 6,940 KB
testcase_17	AC	1 ms 6,940 KB
testcase_18	AC	1 ms 6,940 KB
testcase_19	AC	1 ms 6,940 KB
testcase_20	AC	1 ms 6,940 KB
testcase_21	AC	7 ms 6,944 KB
testcase_22	AC	6 ms 6,944 KB
testcase_23	AC	7 ms 6,940 KB
testcase_24	AC	5 ms 6,940 KB
testcase_25	AC	7 ms 6,940 KB
testcase_26	AC	4 ms 6,940 KB
testcase_27	AC	3 ms 6,940 KB
testcase_28	AC	6 ms 6,944 KB
testcase_29	AC	4 ms 6,944 KB
testcase_30	AC	7 ms 6,940 KB
testcase_31	AC	10 ms 6,940 KB
testcase_32	AC	8 ms 6,944 KB
testcase_33	AC	8 ms 6,944 KB
testcase_34	AC	9 ms 6,940 KB
testcase_35	AC	10 ms 6,940 KB
testcase_36	AC	1 ms 6,940 KB
testcase_37	AC	7 ms 6,944 KB
testcase_38	AC	8 ms 6,944 KB
testcase_39	AC	7 ms 6,940 KB
testcase_40	AC	7 ms 6,940 KB
testcase_41	AC	7 ms 6,944 KB
testcase_42	AC	1 ms 6,944 KB
testcase_43	AC	1 ms 6,944 KB
testcase_44	AC	1 ms 6,944 KB
testcase_45	AC	1 ms 6,940 KB
testcase_46	AC	2 ms 6,944 KB
testcase_47	AC	3 ms 6,940 KB
testcase_48	AC	2 ms 6,944 KB
testcase_49	AC	1 ms 6,944 KB
testcase_50	AC	1 ms 6,940 KB
testcase_51	AC	1 ms 6,944 KB
testcase_52	AC	1 ms 6,944 KB
testcase_53	AC	1 ms 6,940 KB
testcase_54	AC	1 ms 6,940 KB
testcase_55	AC	3 ms 6,940 KB
testcase_56	AC	1 ms 6,940 KB
testcase_57	AC	1 ms 6,944 KB
testcase_58	AC	1 ms 6,944 KB
testcase_59	AC	1 ms 6,940 KB
testcase_60	AC	1 ms 6,944 KB
testcase_61	AC	2 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

package main

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

func main() {
	// demo()
	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
	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的传递闭包 => 690.574ms
	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()
	TransitiveClosure(eye)
	time4 := time.Now()
	fmt.Println(time4.Sub(time3))
}

func NewBooleanMatrix(row, col int) *BooleanMatrix {
	return &BooleanMatrix{ROW: row, COL: col, c: (1 + col>>3), 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
	c        int // 1+COL/8
	x        []uint64
}

func (mat *BooleanMatrix) Get(i, j int) bool {
	return mat.x[(i>>3)*mat.c+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)*mat.c+j>>3] |= (1 << ((i&7)<<3 | j&7))
	} else {
		mat.x[(i>>3)*mat.c+j>>3] &= ^(1 << ((i&7)<<3 | j&7))
	}
}

func (mat *BooleanMatrix) Copy() *BooleanMatrix {
	copied := make([]uint64, len(mat.x))
	copy(copied, mat.x)
	return &BooleanMatrix{ROW: mat.ROW, COL: mat.COL, x: copied}
}

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