hdu 6198 dfs枚举找规律+矩阵乘法

We define a sequence  F :

⋅   F0=0,F1=1 ;
⋅   Fn=Fn−1+Fn−2 (n≥2) .

Give you an integer  k , if a positive number  n  can be expressed by
n=Fa1+Fa2+...+Fak  where  0≤a1≤a2≤⋯≤ak , this positive number is  mjf−good . Otherwise, this positive number is  mjf−bad .
Now, give you an integer  k , you task is to find the minimal positive  mjf−bad  number.
The answer may be too large. Please print the answer modulo 998244353.

There are about 500 test cases, end up with EOF.
Each test case includes an integer  k  which is described above. ( 1≤k≤109 )

For each case, output the minimal  mjf−bad  number mod 998244353.

  
1

  
4

2017 ACM/ICPC Asia Regional Shenyang Online

线dfs枚举出前6项结果发现递推式，注意矩阵中有负数。

import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.StringTokenizer;public class Main {public static void main(String[] args) {new Task().solve();}
}class Task {InputReader in = new InputReader(System.in) ;PrintWriter out = new PrintWriter(System.out) ;/*    long[] fib = new long[25] ;{fib[1] = 0 ;fib[2] = 1 ;for(int i = 3 ; i < 25 ; i++){fib[i] = fib[i-1] + fib[i-2] ; }}Set<Long> h ;int n ; int[] sel ;void dfs(int id , int s){if(s == n){long sum = 0 ; for(int i = 0 ; i < n ; i++){sum += fib[sel[i]] ;}h.add(sum) ;return ;}for(int i = id ; i < 25 ; i++){sel[s] = i ; dfs(id , s+1) ;}}void solve(){n = 6 ;sel = new int[n] ;h = new TreeSet<Long>() ;dfs(1 , 0) ;long i = 1 ;while(true){if(! h.contains(i)){System.out.println(i) ;break ; }i++ ;}out.flush() ;}*/void solve(){while(in.hasNext()){int k = in.nextInt() ;long res = 0 ;if(k == 1){res = 4 ;}else if(k == 2){res = 12 ;}else{Mat A = new Mat(new long[][]{{3,-1,1},{1,0,0},{0,0,1}}) ;A = pow(A, k-2) ;res += A.val[0][0] * 12 % Mod ;res += A.val[0][1] * 4 % Mod  ;res += A.val[0][2] ;res %= Mod ;res += Mod ;res %= Mod ;}out.println(res) ;  //out.flush(); }out.flush() ; }final long Mod = 998244353L ;class Mat{long[][] val = new long[3][3] ;Mat(long [][] val){this.val = val ;}Mat(int type){for(int i = 0 ; i < 3 ; i++){Arrays.fill(val[i] , 0) ;}if(type == 1){val[0][0] = val[1][1] = val[2][2] = 1L ;}}}Mat mult(Mat x , Mat y){Mat s = new Mat(0) ;for(int i = 0 ; i < 3 ; i++){for(int j = 0 ; j < 3 ; j++){for(int k = 0 ; k < 3 ; k++){s.val[i][j] += x.val[i][k] * y.val[k][j] ;s.val[i][j] %= Mod ;}}}return s ;}Mat pow(Mat x , int y){Mat s = new Mat(1) ;for(; y > 0 ; y >>= 1){if((y & 1) > 0){s = mult(s, x) ;}x = mult(x, x) ;}return s ; }
}class InputReader {    public BufferedReader reader;    public StringTokenizer tokenizer;    public InputReader(InputStream stream) {    reader = new BufferedReader(new InputStreamReader(stream), 32768);    tokenizer = new StringTokenizer("");    }    private void eat(String s) {    tokenizer = new StringTokenizer(s);    }    public String nextLine() {     try {    return reader.readLine();    } catch (Exception e) {    return null;    }    }    public boolean hasNext() {    while (!tokenizer.hasMoreTokens()) {    String s = nextLine();    if (s == null)    return false;    eat(s);    }    return true;    }    public String next() {    hasNext();    return tokenizer.nextToken();    }    public int nextInt() {    return Integer.parseInt(next());    }    public int[] nextInts(int n) {    int[] nums = new int[n];    for (int i = 0; i < n; i++) {    nums[i] = nextInt();    }    return nums;    }    public long nextLong() {    return Long.parseLong(next());    }    public double nextDouble() {    return Double.parseDouble(next());    }    public BigInteger nextBigInteger() {    return new BigInteger(next());    }    }