Programming Challenge -PKU- 2440 DNA

※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

2440 DNA

問題

解答方針

長さ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;
    }
}