2440 DNA

「2440 DNA」の編集履歴（バックアップ）一覧はこちら

「2440 DNA」(2006/04/17 (月) 02:19:42) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

**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;
     }
 }