結果

問題 No.1448 和差算
コンテスト
ユーザー ID 21712
提出日時 2026-05-25 14:47:32
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,510 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 17,846 ms
コンパイル使用メモリ 279,848 KB
実行使用メモリ 7,968 KB
最終ジャッジ日時 2026-05-25 14:47:57
合計ジャッジ時間 12,514 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

import . "fmt"
import . "math/big"

const M = 1e9+7

func main() {
	var a,b,c,d,n int
	Scan(&a,&b,&c,&d,&n)
	if n == 0 {
		ans := (b+d)%M
		Println((ans+M)%M)
		return
	}
	var ans int
	p := n/4
	switch n%4 {
		case 0:
			if p%2 == 0 {
				ans = (b+d)%M
			} else {
				ans = (a+c)%M
			}
		case 1:
			if p%2 == 0 {
				ans = b*2%M
			} else {
				ans = a*2%M
			}
		case 2:
			if p%2 == 0 {
				ans = (b-c)%M*2%M
			} else {
				ans = (a-d)%M*2%M
			}
		case 3:
			if p%2 == 0 {
				ans = -4*c%M
			} else {
				ans = -4*d%M
			}
	}
	
	if p > 0 {
		k := int(new(Int).Exp(
			NewInt(-4),
			NewInt(int64(p)),
			NewInt(M),
		).Int64())
		ans = (k*ans)%M
	}

	Println((ans+M)%M)
}

/*
考察

行列累乗とやらに見える

|a[i]| = |1 -1| * |a[i-1]| = |1 -1| * |1 -1| * |a[i-2]|
|b[i]|   |1  1|   |b[i-1]|   |1  1|   |1  1|   |b[i-2]|

|1 -1| * |1 -1| = |0 -2| = 2 * |0 -1|
|1  1|   |1  1|   |2  0|       |1  0|

|1 -1| ^ 3 = |0 -2| * |1 -1| = |-2 -2| = 2 * |-1 -1|
|1  1|       |2  0|   |1  1|   | 2 -2|       | 1 -1|

|1 -1| ^ 4 = |-2 -2| * |1 -1| = |-4  0| = -4 * |1 0|
|1  1|       | 2 -2|   |1  1|   | 0 -4|        |0 1|

4乗で単位行列が出てきちゃったので
5乗(5=1+4)は1乗の-4倍
6乗(6=2+4)は2乗の-4倍
7乗(7=3+4)は3乗の-4倍
8乗(8=4+4)は4乗の-4倍
9乗(9=1+4+4)は1乗の(-4)^2倍
10乗(10=2+4+4)は2乗の(-4)^2倍
11乗(11=3+4+4)は3乗の(-4)^2倍
12乗(12=4+4+4)は4乗の(-4)^2倍

|a[i]| = |1 -1| ^ i * |a[0]|
|b[i]|   |1  1|       |b[0]|

行列の符号と(-4)^Pの符号との関係を見て
a[0]とb[0]を選べばよい
a[0]はAかBの両端のどっちか
b[0]はCかDの両端のどっちか
だと思うけど、中間の値のほうが良い場合ある？1次式で単調変化ぽい気がするし両端でいい気がするけど

N=(1+4*P)乗の場合
|a[N]| = (-4)^P * |1 -1| * |a[0]|
|b[N]|            |1  1|   |b[0]|
は
a[N]+b[N] = (-4)^P * ((a[0] - b[0]) + (a[0] + b[0]))
          = (-4)^P * 2 * a[0]

N=(2+4*P)乗の場合
|a[N]| = (-4)^P * 2 * |0 -1| * |a[0]|
|b[N]|                |1  0|   |b[0]|
は
a[N]+b[N] = (-4)^P * 2 * (-b[0] + a[0])

N=(3+4*P)乗の場合
|a[N]| = (-4)^P * 2 * |-1 -1| * |a[0]|
|b[N]|                | 1 -1|   |b[0]|
は
a[N]+b[N] = (-4)^P * 2 * ((-a[0] - b[0]) + (a[0] - b[0]))
          = (-4)^P * 2 * (-2) * b[0]

N=(4+4*P)乗の場合
|a[N]| = (-4)^P * (-4) * |1 0| * |a[0]|
|b[N]|                   |0 1|   |b[0]|
は
a[N]+b[N] = (-4)^(P+1) * (a[0] + b[0])

これ
b[N+1] = a[N]+b[N] だね…


*/
0