結果

問題 No.720 行列のできるフィボナッチ数列道場 (2)
ユーザー 37zigen37zigen
提出日時 2018-07-29 01:57:49
言語 Java21
(openjdk 21)
結果
AC  
実行時間 110 ms / 2,000 ms
コード長 1,701 bytes
コンパイル時間 1,961 ms
コンパイル使用メモリ 78,060 KB
実行使用メモリ 54,160 KB
最終ジャッジ日時 2024-07-07 03:11:50
合計ジャッジ時間 5,108 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 108 ms
54,116 KB
testcase_01 AC 95 ms
52,544 KB
testcase_02 AC 106 ms
53,864 KB
testcase_03 AC 109 ms
53,828 KB
testcase_04 AC 102 ms
52,632 KB
testcase_05 AC 104 ms
53,108 KB
testcase_06 AC 106 ms
54,064 KB
testcase_07 AC 95 ms
52,996 KB
testcase_08 AC 98 ms
52,876 KB
testcase_09 AC 109 ms
54,160 KB
testcase_10 AC 102 ms
52,936 KB
testcase_11 AC 107 ms
53,732 KB
testcase_12 AC 100 ms
53,108 KB
testcase_13 AC 100 ms
53,024 KB
testcase_14 AC 103 ms
53,056 KB
testcase_15 AC 98 ms
53,920 KB
testcase_16 AC 100 ms
52,640 KB
testcase_17 AC 110 ms
54,044 KB
testcase_18 AC 97 ms
52,900 KB
testcase_19 AC 106 ms
53,872 KB
testcase_20 AC 92 ms
52,296 KB
testcase_21 AC 97 ms
52,784 KB
testcase_22 AC 106 ms
54,016 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		new Main().run();
	}

	void run() {
		Scanner sc = new Scanner(System.in);
		V v1 = new V(inv(2), inv(2));
		V v2 = new V(inv(2), -inv(2));
		V ans = new V(0, 0);
		long N = sc.nextLong();
		long M = sc.nextLong();
		v1 = v1.pow(M);
		v2 = v2.pow(M);
		ans = v1.sum(N).sub(v2.sum(N));
		System.out.println(ans.b);
	}

	class V {
		long a;
		long b;

		public V(long a_, long b_) {
			a = a_ % MOD;
			b = b_ % MOD;
		}

		V mul(V o) {
			return new V(a * o.a % MOD + 5 * b * o.b % MOD, a * o.b % MOD + o.a * b % MOD);
		}

		V add(V o) {
			return new V(a + o.a, b + o.b);
		}

		V sub(V o) {
			return new V((a - o.a + MOD) % MOD, (b - o.b + MOD) % MOD);
		}

		V conj() {
			return new V(a, (MOD - b) % MOD);
		}

		V div(V o) {
			long coe = inv((o.a * o.a % MOD - o.b * o.b % MOD * 5 % MOD + MOD) % MOD);
			V v = this.mul(o.conj());
			return new V(v.a * coe % MOD, v.b * coe % MOD);
		}

		V pow(long n) {
			V ret = new V(1, 0);
			V p = new V(a, b);
			for (; n > 0; n >>= 1, p = p.mul(p)) {
				if (n % 2 == 1) {
					ret = ret.mul(p);
				}
			}
			return ret;
		}

		V sum(long n) {
			V ret = new V(0, 0);
			ret = ret.add(this.pow(n + 1));
			ret = ret.sub(this);
			ret = ret.div(this.sub(new V(1, 0)));
			return ret;
		}

	}

	long MOD = 1000000007;

	long pow(long a, long n) {
		long ret = 1;
		for (; n > 0; n >>= 1, a = a * a % MOD) {
			if (n % 2 == 1)
				ret = ret * a % MOD;
		}
		return ret;
	}

	long inv(long a) {
		return pow(a, MOD - 2);
	}

	void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}
}
0