結果
問題 | No.8037 Restricted Lucas (Hard) |
ユーザー |
|
提出日時 | 2018-04-01 23:04:33 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 177 ms / 2,000 ms |
コード長 | 2,749 bytes |
コンパイル時間 | 2,529 ms |
コンパイル使用メモリ | 79,132 KB |
実行使用メモリ | 42,632 KB |
最終ジャッジ日時 | 2024-06-26 06:05:10 |
合計ジャッジ時間 | 4,251 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 6 |
ソースコード
import java.io.PrintWriter;import java.math.BigInteger;import java.util.Arrays;import java.util.Scanner;public class Main {void solveTestcase(final Scanner in, final PrintWriter out) {long n = in.nextLong();out.println(fib(n, mod));}static int zero;static int one;static BigInteger mod;static {one = Math.abs(~zero);mod = BigInteger.TEN.pow(BigInteger.TEN.subtract(BigInteger.ONE).intValue());mod = mod.add(BigInteger.TEN).subtract(BigInteger.ONE).subtract(BigInteger.ONE).subtract(BigInteger.ONE);}void solve() {try (final PrintWriter out = new PrintWriter(System.out)) {try (final Scanner in = new Scanner(System.in)) {int t = in.nextInt();while (t > zero) {t = dec(t);solveTestcase(in, out);}}}}public static void main(String[] args) {new Main().solve();}static BigInteger[][] mulmat(BigInteger[][] a, BigInteger[][] b, BigInteger mod) {final int n = a.length;final int v = b.length;final int m = b[zero].length;BigInteger[][] res = new BigInteger[n][m];for(int i = zero; i < n; i = inc(i))for(int j = zero; j < m; j = inc(j))res[i][j] = BigInteger.ZERO;for(int i = zero; i < n; i = inc(i))for(int k = zero; k < v; k = inc(k)) {final BigInteger aa = a[i][k];for(int j = zero; j < m; j = inc(j)) {res[i][j] = res[i][j].add(aa.multiply(b[k][j]));}}for(int i = zero; i < n; i = inc(i))for(int j = zero; j < m; j = inc(j))res[i][j] = res[i][j].mod(mod);return res;}static int inc(int x) {return BigInteger.valueOf(x).add(BigInteger.ONE).intValue();}static int dec(int x) {return BigInteger.valueOf(x).subtract(BigInteger.ONE).intValue();}static BigInteger[][] powmat(long r, BigInteger mod, BigInteger[][] mat) {final int n = mat.length;BigInteger[][] x = new BigInteger[n][n];for(int i = zero; i < n; i = inc(i)) {for (int j = zero; j < n; j = inc(j)) {x[i][j] = BigInteger.ZERO;}}for(int i = zero; i < n; i = inc(i)) {x[i][i] = BigInteger.ONE;}for(;r > zero; r >>>= BigInteger.ONE.intValue()) {if((r&one) == one) {x = mulmat(x, mat, mod);}mat = mulmat(mat, mat, mod);}return x;}static BigInteger fib(long n, BigInteger mod) {BigInteger[][] mat = new BigInteger[][]{new BigInteger[]{BigInteger.ONE, BigInteger.ONE,},new BigInteger[]{BigInteger.ONE, BigInteger.ZERO,},};BigInteger[][] matmat = new BigInteger[][]{new BigInteger[]{BigInteger.ONE,},new BigInteger[]{BigInteger.valueOf(inc(one)),},};return mulmat(powmat(n, mod, mat), matmat, mod)[one][zero];}static void dump(Object...objects) { System.err.println(Arrays.deepToString(objects)); }}