結果
問題 | No.194 フィボナッチ数列の理解(1) |
ユーザー | aru aru |
提出日時 | 2020-09-08 22:29:12 |
言語 | Go (1.23.4) |
結果 |
AC
|
実行時間 | 27 ms / 5,000 ms |
コード長 | 2,799 bytes |
コンパイル時間 | 13,632 ms |
コンパイル使用メモリ | 226,544 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-30 10:22:22 |
合計ジャッジ時間 | 13,225 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
package mainimport ("bufio""fmt""os""sort""strconv")func out(x ...interface{}) {fmt.Println(x...)}var sc = bufio.NewScanner(os.Stdin)func getInt() int {sc.Scan()i, e := strconv.Atoi(sc.Text())if e != nil {panic(e)}return i}func getInts(N int) []int {ret := make([]int, N)for i := 0; i < N; i++ {ret[i] = getInt()}return ret}func getString() string {sc.Scan()return sc.Text()}// min, max, asub, absなど基本関数func max(a, b int) int {if a > b {return a}return b}func min(a, b int) int {if a < b {return a}return b}func asub(a, b int) int {if a > b {return a - b}return b - a}func abs(a int) int {if a >= 0 {return a}return -a}func lowerBound(a []int, x int) int {idx := sort.Search(len(a), func(i int) bool {return a[i] >= x})return idx}func upperBound(a []int, x int) int {idx := sort.Search(len(a), func(i int) bool {return a[i] > x})return idx}const mod = int(1e9 + 7)func solve1(N, K int, a []int) {K = min(1000000, K)sum := 0for i := 0; i < N; i++ {sum += a[i]}f := sums := sumfor i := N; i < K; i++ {f = sums += sums %= mod// out(f, s)x := a[i%N]a[i%N] = sumsum += sum - xsum %= modif sum < 0 {sum += mod}}out(f, s)}func mulMod(A, B [][]int) [][]int {H := len(A)W := len(B[0])K := len(A[0])C := make([][]int, W)for i := 0; i < W; i++ {C[i] = make([]int, W)}for i := 0; i < H; i++ {for j := 0; j < W; j++ {for k := 0; k < K; k++ {C[i][j] += A[i][k] * B[k][j]C[i][j] %= mod}}}return C}func powModMatrix(A [][]int, p int) [][]int {N := len(A)ret := make([][]int, N)for i := 0; i < N; i++ {ret[i] = make([]int, N)ret[i][i] = 1}for p > 0 {if p&1 == 1 {ret = mulMod(ret, A)}A = mulMod(A, A)p >>= 1}return ret}func solve2(N, K int, x []int) {a := make([][]int, N)for i := 0; i < N; i++ {a[i] = make([]int, N)}for i := 0; i < N; i++ {a[0][i] = 1}for i := 1; i < N; i++ {a[i][i-1] = 1}a = powModMatrix(a, K-N)f := 0for i := 0; i < N; i++ {f += x[N-1-i] * a[0][i]f %= mod}a = make([][]int, N+1)for i := 0; i < N+1; i++ {a[i] = make([]int, N+1)}a[0][0] = 2a[0][N] = -1for i := 1; i < N+1; i++ {a[i][i-1] = 1}// for i := 0; i < N+1; i++ {// out(a[i])// }a = powModMatrix(a, K-N)y := make([]int, N+1)y[0] = 0for i := 1; i < N+1; i++ {y[i] = y[i-1] + x[i-1]}// out(y)s := 0for i := 0; i < N+1; i++ {s += y[N-i] * a[0][i]s %= modif s < 0 {s += mod}}out(f, s)}func main() {sc.Split(bufio.ScanWords)N, K := getInt(), getInt()a := getInts(N)if K > 1000000 {solve2(N, K, a)} else {solve1(N, K, a)}}