結果

問題 No.8037 Restricted Lucas (Hard)
ユーザー uafr_cs
提出日時 2018-04-01 23:28:41
言語 Java
(openjdk 23)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other WA * 6
権限があれば一括ダウンロードができます

ソースコード

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