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