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;
}
}
最終更新:2006年04月17日 02:19