結果
問題 | No.534 フィボナッチフィボナッチ数 |
ユーザー |
![]() |
提出日時 | 2017-06-24 18:40:13 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 128 ms / 2,000 ms |
コード長 | 1,508 bytes |
コンパイル時間 | 1,881 ms |
コンパイル使用メモリ | 77,180 KB |
実行使用メモリ | 41,680 KB |
最終ジャッジ日時 | 2024-10-04 02:58:27 |
合計ジャッジ時間 | 7,663 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 42 |
ソースコード
import java.util.*;public class Main {static long MOD1 = (long)Math.pow(10, 9) + 7;static long MOD2 = 2 * (long)Math.pow(10, 9) + 16;public static void main(String[] args) {Scanner sc = new Scanner(System.in);long n = sc.nextLong();long[][] d = new long[2][2];d[0][0] = 1;d[0][1] = 1;d[1][0] = 1;long[][] f = func(d, n, MOD2);long t = f[1][0];long[][] ans = func(d, t, MOD1);long anse = ans[1][0];System.out.println(anse);}public static long[][] func(long[][] a, long x, long mod) {if(x == 0) {long[][] b = new long[2][2];b[0][0] = 1;b[1][1] = 1;return b;}long[][] c = func(a, x / 2, mod);long[][] d = new long[2][2];d[0][0] = (((c[0][0] * c[0][0]) % mod) + ((c[0][1] * c[1][0]) % mod)) % mod;d[0][1] = (((c[0][0] * c[0][1]) % mod) + ((c[0][1] * c[1][1]) % mod)) % mod;d[1][0] = (((c[1][0] * c[0][0]) % mod) + ((c[1][1] * c[1][0]) % mod)) % mod;d[1][1] = (((c[1][0] * c[0][1]) % mod) + ((c[1][1] * c[1][1]) % mod)) % mod;if(x % 2 == 0) {return d;} else {long[][] e = new long[2][2];e[0][0] = (((a[0][0] * d[0][0]) % mod) + ((a[0][1] * d[1][0]) % mod)) % mod;e[0][1] = (((a[0][0] * d[0][1]) % mod) + ((a[0][1] * d[1][1]) % mod)) % mod;e[1][0] = (((a[1][0] * d[0][0]) % mod) + ((a[1][1] * d[1][0]) % mod)) % mod;e[1][1] = (((a[1][0] * d[0][1]) % mod) + ((a[1][1] * d[1][1]) % mod)) % mod;return e;}}}