結果

問題 No.8037 Restricted Lucas (Hard)
ユーザー tanzaku
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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)); }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0