結果

問題 No.3036 Restricted Lucas (Easy)
ユーザー uafr_csuafr_cs
提出日時 2018-04-01 23:21:31
言語 Java21
(openjdk 21)
結果
WA  
実行時間 -
コード長 2,209 bytes
コンパイル時間 2,336 ms
コンパイル使用メモリ 77,932 KB
実行使用メモリ 58,064 KB
最終ジャッジ日時 2024-06-26 06:07:04
合計ジャッジ時間 4,437 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.math.BigInteger;
import java.util.Arrays;
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[][] mat1, BigInteger[][] mat2){
		BigInteger[][] ret = new BigInteger[two][two];
		
		ret[zero][zero] = mat1[zero][zero].multiply(mat2[zero][zero]).add(mat1[zero][one].multiply(mat2[one][zero])).mod(MOD);
		ret[zero][one]  = mat1[zero][zero].multiply(mat2[zero][one]).add(mat1[zero][one].multiply(mat2[one][one])).mod(MOD);
		
		ret[one][zero] = mat1[one][zero].multiply(mat2[zero][zero]).add(mat1[one][one].multiply(mat2[one][zero])).mod(MOD);
		ret[one][one] = mat1[one][zero].multiply(mat2[zero][one]).add(mat1[one][one].multiply(mat2[one][one])).mod(MOD);
		
		return ret;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		final int T = sc.nextInt();
		while(sc.hasNext()){
			final BigInteger N = BigInteger.valueOf(sc.nextLong());
			
			if(N.equals(ZERO)){
				System.out.println(TWO);
			}else{
				BigInteger[][] mat = {{ZERO, ONE}, {ONE, ONE}};
				BigInteger[][] ret = mat_pow(mat, N);
				
				BigInteger answer = ret[zero][zero].multiply(TWO).add(ret[zero][one]).mod(MOD);
				System.out.println(answer);
				
			}
			
			
		}
	}
}
0