2013
11-11

# DNA

A kind of virus has attacked the X planet, and many lives are infected. After weeks of study, The CHO (Creature Healthy Organization) of X planet finally finds out that this kind of virus has two kind of very simple DNA, and can be represented by 101 and 111. Unfortunately, the lives on the planet also have DNA formed by 0s and 1s. If a creature’s DNA contains the virus’ DNA, it will be affected; otherwise it will not. Given an integer L, it is clear that there will be 2 ^ L different lives, of which the length of DNA is L. Your job is to find out in the 2 ^ L lives how many won’t be affected?

The input contains several test cases. For each test case it contains a positive integer L (1 <= L <= 10 ^ 8). The end of input is indicated by end-of-file.

For each test case, output K mod 2005, here K is the number of lives that will not be affected.

4

9

import java.util.Scanner;

public class Main {
public static int[][] org;
public static int[][] m;
public static int[][] f = new int[4][1];
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
while(cin.hasNext()) {
int n = cin.nextInt();
if(test(n))
continue;
reset();
n = n-6;
while(n != 0) {
if(n % 2 != 0) {
org = mul(org, m);
}
n = n / 2;
m = mul(m, m);
}

f = mul(org, f);
System.out.println(f[0][0]%2005);
}
}

private static int[][] mul(int[][] a, int[][] b) {
int row = a.length;
int col = b[0].length;
int[][] test = new int[row][col];
for (int i = 0; i< row; i++) {
for (int j = 0; j< col; j++) {
for (int k = 0; k< a[0].length; k++) {
test[i][j]=test[i][j]+a[i][k]*b[k][j];
}
test[i][j] = test[i][j] % 2005;
}
}
return test;
}

private static void reset() {
org = new int[4][4];
int size = org.length;
for(int i=0; i< size; i++) {
org[i][i] = 1;
}
m = new int[4][4];
m[0][0] = 1;
m[0][1] = 0;
m[0][2] = 1;
m[0][3] = 1;
for(int i=1; i< size; i++) {
m[i][i-1] = 1;
}
f[0][0] = 25;
f[1][0] = 15;
f[2][0] = 9;
f[3][0] = 6;
}

private static boolean test(int n) {
if(n == 3) {
System.out.println(6);
return true;
}
else if(n == 4) {
System.out.println(9);
return true;
}
else if(n == 5) {
System.out.println(15);
return true;
}
else if(n == 6) {
System.out.println(25);
return true;
}else if(n == 1) {
System.out.println(2);
return true;
}else if(n == 2) {
System.out.println(4);
return true;
}else if(n == 0) {
System.out.println(1);
return true;
}
return false;
}

}

1. 如果两个序列的最后字符不匹配（即X [M-1]！= Y [N-1]）
L（X [0 .. M-1]，Y [0 .. N-1]）= MAX（L（X [0 .. M-2]，Y [0 .. N-1]），L（X [0 .. M-1]，Y [0 .. N-1]）
这里写错了吧。