結果

問題 No.3037 Restricted Lucas (Hard)
ユーザー uafr_csuafr_cs
提出日時 2018-04-01 23:28:41
言語 Java21
(openjdk 21)
結果
WA  
実行時間 -
コード長 2,239 bytes
コンパイル時間 2,421 ms
コンパイル使用メモリ 77,388 KB
実行使用メモリ 42,600 KB
最終ジャッジ日時 2024-06-26 06:08:03
合計ジャッジ時間 3,991 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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.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);
		
		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