結果

問題 No.1136 Four Points Tour
ユーザー ID 21712
提出日時 2026-06-07 14:06:03
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
AC  
実行時間 1 ms / 2,000 ms
コード長 1,381 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 13,193 ms
コンパイル使用メモリ 289,816 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-06-07 14:06:20
合計ジャッジ時間 15,378 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge3_0
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

import . "fmt"

func main() {
	var n int
	Scan(&n)
	
	m := newMat(
		0,1,1,1,
		1,0,1,1,
		1,1,0,1,
		1,1,1,0,
	)
	
	v := newVec(1,0,0,0)
	
	ans := m.pow(n).mulVec(v).t[0]
	
	Println(ans)
}

const M = 1e9+7
const S = 4

type Mat struct {
	t [S][S]int
}

type Vec struct {
	t [S]int
}

func newMat(params ...int) *Mat {
	r := &Mat{}
	for i := 0; i < S && len(params) > 0; i++ {
		copy(r.t[i][:], params)
		params = params[min(S,len(params)):]
	}
	return r
}

func newVec(params ...int) *Vec {
	r := &Vec{}
	copy(r.t[:], params)
	return r
}

func (m1 *Mat) mulMat(m2 *Mat) *Mat {
	r := &Mat{}
	for row := 0; row < S; row++ {
		for col := 0; col < S; col++ {
			for k := 0; k < S; k++ {
				r.t[row][col] += m1.t[row][k] * m2.t[k][col] % M
				r.t[row][col] %= M
			}
		}
	}
	return r
}

func (m *Mat) pow(p int) *Mat {
	x := m
	r := newMat(
		1,0,0,0,
		0,1,0,0,
		0,0,1,0,
		0,0,0,1,
	)
	for p > 0 {
		if p % 2 != 0 {
			r = r.mulMat(x)
		}
		x = x.mulMat(x)
		p /= 2
	}
	return r
}

func  (m *Mat) mulVec(v *Vec) *Vec {
	r := &Vec{}
	for row := 0; row < S; row++ {
		for k := 0; k < S; k++ {
			r.t[row] += m.t[row][k] * v.t[k] % M
			r.t[row] %= M
		}
	}	
	return r
}


/*
考察

行列累乗の問題に見える


| A[N] |   | 0 1 1 1 |^N   | A[0] |
| B[N] | = | 1 0 1 1 |   * | B[0] |
| C[N] |   | 1 1 0 1 |     | C[0] |
| D[N] |   | 1 1 1 0 |     | D[0] |



*/
0