2440 DNA

2440 DNA

問題

http://acm.pku.edu.cn/JudgeOnline/problem?id=2440

解答方針

長さn(n>=3)の0,1の列で"010"，"111"を含まないもののうち，先頭の2文字が"00"のものをCn0，"01"のものをCn1，"10"のものをCn2，"11"のものをCn3とおいて，C(n+1)0，C(n+1)1，C(n+1)2，C(n+1)3をCn0，Cn1，Cn2，Cn3の式で表す．Xn = (Cn0, Cn1, Cn2, Cn3) とおくと，X(n+1) = A Xn (Aは4x4定数行列，具体的な形は省略) とかけるので，Xn = A^(n-3) X3とかける．行列の掛け算はO(log n)で実行できるので，全体がO(log n)で実行できる．

解答例

import java.util.*;

public class Main {
    final static int I[][] = {{1,0,0,0},{0,1,0,0},{0,0,1,0},{0,0,0,1}};
    final static int A[][] = {{1,1,0,0},{0,0,1,1},{1,0,0,0},{0,0,1,0}};
    final static int F[] = {2,2,1,1};
    final static int mod = 2005;

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            int ans = answer(n);
            System.out.println(ans);
        }
    }
    
    public static int answer(int n){
        if(n==1) return 2;
        else if(n==2) return 4;
        else{
            int m[][] = exp(n-3);
            int x[] = new int[4];
            for(int i=0;i<4;i++){
                x[i] = 0;
                for(int j=0;j<4;j++){
                    x[i] += m[i][j]*F[j];
                }
                x[i] %= mod;
            }
            return (x[0]+x[1]+x[2]+x[3]) % mod;
        }
    }

    public static int[][] exp(int n){
        if(n==0) return I;
        else if(n==1) return A;
        else if(n%2==0){
            int m[][] = exp(n/2);
            return mul(m,m);
        }
        else{
            return mul(exp(n-1),A);
        }
        
    }
    public static int[][] mul(int a[][],int b[][]){
        int m[][] = new int[4][4];
        for(int i=0;i<4;i++){
            for(int j=0;j<4;j++){
                m[i][j] = 0;
                for(int k=0;k<4;k++){
                    m[i][j] += a[i][k]*b[k][j];
                }
                m[i][j] %= mod;
            }
        }
        return m;
    }
}