結果

問題 No.720 行列のできるフィボナッチ数列道場 (2)
コンテスト
ユーザー 37zigen
提出日時 2018-07-29 01:57:49
言語 Java
(openjdk 23)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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