結果

問題 No.3037 Restricted Lucas (Hard)
ユーザー uafr_csuafr_cs
提出日時 2018-04-01 23:30:53
言語 Java21
(openjdk 21)
結果
AC  
実行時間 165 ms / 2,000 ms
コード長 2,257 bytes
コンパイル時間 2,419 ms
コンパイル使用メモリ 77,464 KB
実行使用メモリ 42,556 KB
最終ジャッジ日時 2024-06-26 06:09:07
合計ジャッジ時間 4,082 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 143 ms
41,512 KB
testcase_01 AC 159 ms
41,840 KB
testcase_02 AC 155 ms
42,064 KB
testcase_03 AC 152 ms
42,268 KB
testcase_04 AC 155 ms
42,320 KB
testcase_05 AC 165 ms
42,556 KB
testcase_06 AC 164 ms
42,224 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
	
	public static final BigInteger ZERO = BigInteger.ZERO;
	public static final BigInteger ONE = BigInteger.ONE;
	public static final BigInteger TWO = ONE.add(ONE);
	public static final BigInteger FIVE = TWO.multiply(TWO).add(ONE);
	public static final BigInteger SEVEN = FIVE.add(TWO);
	public static final BigInteger TEN = BigInteger.TEN;
	public static final BigInteger MOD = 
			TEN.multiply(TEN).multiply(TEN).multiply(TEN).multiply(TEN).multiply(TEN).multiply(TEN).multiply(TEN).multiply(TEN).add(SEVEN);
	
	public static final int zero = ZERO.intValue();
	public static final int one = ONE.intValue();
	public static final int two = TWO.intValue();
	
	public static BigInteger[][] mat_pow(BigInteger[][] mat, BigInteger pow){
		if(pow.equals(ONE)){
			return mat;
		}else if(pow.mod(TWO).equals(ZERO)){
			final BigInteger[][] ret = mat_pow(mat, pow.divide(TWO));
			return mat_mul(ret, ret);
		}else{
			return mat_mul(mat, mat_pow(mat, pow.subtract(ONE)));
		}
	}
	
	public static BigInteger[][] mat_mul(BigInteger[][] mat_X, BigInteger[][] mat_Y){
		BigInteger[][] ret = new BigInteger[two][two];
		
		ret[zero][zero] = mat_X[zero][zero].multiply(mat_Y[zero][zero]).add(mat_X[zero][one].multiply(mat_Y[one][zero])).mod(MOD);
		ret[zero][one]  = mat_X[zero][zero].multiply(mat_Y[zero][one]).add(mat_X[zero][one].multiply(mat_Y[one][one])).mod(MOD);
		
		ret[one][zero] = mat_X[one][zero].multiply(mat_Y[zero][zero]).add(mat_X[one][one].multiply(mat_Y[one][zero])).mod(MOD);
		ret[one][one] = mat_X[one][zero].multiply(mat_Y[zero][one]).add(mat_X[one][one].multiply(mat_Y[one][one])).mod(MOD);
		
		return ret;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		BigInteger T = BigInteger.valueOf(sc.nextLong());
		while(T.compareTo(ZERO) != zero){ T = T.subtract(ONE);
			final BigInteger N = BigInteger.valueOf(sc.nextLong());
			
			if(N.equals(ZERO)){
				System.out.println(TWO);
			}else{
				final BigInteger[][] mat = {{ZERO, ONE}, {ONE, ONE}};
				final BigInteger[][] ret = mat_pow(mat, N);
				
				BigInteger answer = ret[zero][zero].multiply(TWO).add(ret[zero][one]).mod(MOD);
				System.out.println(answer);
			}
		}
	}
}
0