結果

問題 No.658 テトラナッチ数列 Hard
コンテスト
ユーザー threepipes_s
提出日時 2018-03-02 22:37:40
言語 Java
(openjdk 23)
結果
AC  
実行時間 412 ms / 2,000 ms
コード長 5,795 bytes
コンパイル時間 2,611 ms
コンパイル使用メモリ 89,672 KB
実行使用メモリ 57,936 KB
最終ジャッジ日時 2024-06-13 04:11:26
合計ジャッジ時間 5,690 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.Closeable;
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.lang.reflect.Array;
import java.util.*;

public class Main implements Runnable {
    static ContestScanner in;
    static Writer out;
    public static void main(String[] args) {
        new Thread(null, new Main(), "", 16 * 1024 * 1024).start();
    }

    public void run() {
        Main main = new Main();
        try {
            in = new ContestScanner();
            out = new Writer();
            main.solve();
            out.close();
            in.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    void solve() throws IOException {
        Kitamasa kit = new Kitamasa();
        int q = in.nextInt();
        for (int i = 0; i < q; i++) {
            long[] a = {1, 1, 1, 1};
            long n = in.nextLong();
            if(n < 4) out.println(0);
            else out.println(kit.kitamasa(a, n)[0]);
        }
    }

    class Kitamasa {
        final long mod = 17;
        long[] nextF(long[] a, long[] f) {
            int k = f.length;
            long[] nf = new long[k];
            for(int i = 0; i < k; i++) {
                nf[i] = (nf[i] + a[i] * f[k - 1]) % mod;
                if(i > 0) nf[i] = (nf[i] + f[i - 1]) % mod;
            }
            return nf;
        }

        long[] doubling(long[] a, long[] f) {
            int k = f.length;
            long[] res = new long[k];
            long[] ff = f;
            for(int i = 0; i < k; i++) {
                for(int j = 0; j < k; j++) {
                    res[j] = (res[j] + f[i] * ff[j]) % mod;
                }
                if(i < k - 1) ff = nextF(a, ff);
            }
            return res;
        }

        long[] kitamasa(long[] a, long n) {
            int k = a.length;
            long[] f = new long[k];
            f[0] = 1;
            int size = 64 - Long.numberOfLeadingZeros(n);
            for(int i = size - 1; i >= 0; i--) {
                if((n & 1L << i) > 0) f = nextF(a, f);
                if(i == 0) break;
                f = doubling(a, f);
            }
            return f;
        }

        void dumpExample() {
            long[] a = {2, 3, 4};
            long[][] x = {
                    {1, 0, 0},
                    {0, 1, 0},
                    {0, 0, 1}
            };
            for(int i = 0; i < 10; i++) {
                long[] xi = new long[3];
                for(int j = 0; j < 3; j++) {
                    // xi += x[j] * a[j]
                    for(int k = 0; k < 3; k++) {
                        xi[k] += x[j][k] * a[j];
                    }
                }
                for(int j = 0; j < 2; j++) {
                    x[j] = x[j + 1];
                }
                x[2] = xi;
                System.out.println(Arrays.toString(xi));
            }
        }

        void testNextF() {
            long[] f = {1, 0, 0};
            long[] a = {2, 3, 4};
            for(int i = 0; i < 10; i++) {
                System.out.println(Arrays.toString(f));
                f = nextF(a, f);
            }
        }

        void testDoubling() {
            long[] f = {1, 0, 0};
            long[] a = {2, 3, 4};
            for(int i = 0; i < 10; i++) {
                System.out.println(Arrays.toString(f) +
                        " " + Arrays.toString(doubling(a, f)));
                f = nextF(a, f);
            }
        }

        void testKitamasa() {
            long[] a = {2, 3, 4};
            for(int i = 0; i < 10; i++) {
                System.out.println(Arrays.toString(kitamasa(a, i)));
            }
        }
    }
}

@SuppressWarnings("serial")
class MultiSet<T> extends HashMap<T, Integer>{
    @Override public Integer get(Object key){return containsKey(key)?super.get(key):0;}
    public void add(T key,int v){put(key,get(key)+v);}
    public void add(T key){put(key,get(key)+1);}
    public void sub(T key){final int v=get(key);if(v==1)remove(key);else put(key,v-1);}
    public MultiSet<T> merge(MultiSet<T> set)
    {MultiSet<T>s,l;if(this.size()<set.size()){s=this;l=set;}else{s=set;l=this;}
        for(Entry<T,Integer>e:s.entrySet())l.add(e.getKey(),e.getValue());return l;}
}

class Writer extends PrintWriter{
    public Writer(String filename)throws IOException
    {super(new BufferedWriter(new FileWriter(filename)));}
    public Writer()throws IOException{super(System.out);}
}
class ContestScanner implements Closeable{
    private BufferedReader in;private int c=-2;
    public ContestScanner()throws IOException
    {in=new BufferedReader(new InputStreamReader(System.in));}
    public ContestScanner(String filename)throws IOException
    {in=new BufferedReader(new InputStreamReader(new FileInputStream(filename)));}
    public String nextToken()throws IOException {
        StringBuilder sb=new StringBuilder();
        while((c=in.read())!=-1&&Character.isWhitespace(c));
        while(c!=-1&&!Character.isWhitespace(c)){sb.append((char)c);c=in.read();}
        return sb.toString();
    }
    public String readLine()throws IOException{
        StringBuilder sb=new StringBuilder();if(c==-2)c=in.read();
        while(c!=-1&&c!='\n'&&c!='\r'){sb.append((char)c);c=in.read();}
        return sb.toString();
    }
    public long nextLong()throws IOException,NumberFormatException
    {return Long.parseLong(nextToken());}
    public int nextInt()throws NumberFormatException,IOException
    {return(int)nextLong();}
    public double nextDouble()throws NumberFormatException,IOException
    {return Double.parseDouble(nextToken());}
    public void close() throws IOException {in.close();}
}
0