## HDU 1005 Number Sequence（矩阵），hdu1005

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K
(Java/Others)
Total Submission(s): 177761    Accepted Submission(s): 44124

Problem Description A number sequence is defined as follows:

f(1) = 1, f(2) = 1, f(n) = (A * f(n – 1) + B * f(n – 2)) mod 7.

Given A, B, and n, you are to calculate the value of f(n).

Input The input consists of multiple test cases. Each test case contains
3 integers A, B and n on a single line (1 <= A, B <= 1000, 1 <=
n <= 100,000,000). Three zeros signal the end of input and this test
case is not to be processed.

Output For each test case, print the value of f(n) on a single line.

Sample Input 1 1 3 1 2 10 0 0 0

Sample Output 2 5

Author CHEN, Shunbao

Source ZJCPC2004

Recommend   JGShining   |   We have carefully selected several similar
problems for you:  1008 1004 1021 1019 1002 `````` 1 #include<cstdio>
2 #include<cstring>
3 #include<iostream>
4 using namespace std;
5 const int MAXN=1001;
6 inline void read(int &n){char c='+';bool flag=0;n=0;
7 while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar();
8 while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;}
9 struct matrix
10 {
11     int m;matrix(){memset(m,0,sizeof(m));}
12 };
13 matrix ma;
14 int limit=2;
15 const int mod=7;
16 matrix mul(matrix a,matrix b)
17 {
18     matrix c;
19     for(int k=0;k<limit;k++)
20         for(int i=0;i<limit;i++)
21             for(int j=0;j<limit;j++)
22                 c.m[i][j]=(c.m[i][j]+(a.m[i][k]*b.m[k][j]))%mod;
23     return c;
24 }
25 matrix fast_martix_pow(matrix ma,int p)
26 {
27     matrix bg;
28     bg.m=1;bg.m=1;
29     bg.m=0;bg.m=0;
30     /*for(int i=0;i<limit;i++)
31     {
32         for(int j=0;j<limit;j++)
33             cout<<bg.m[i][j]<<" ";
34         cout<<endl;
35     }*/
36
37     while(p)
38     {
39         if(p&1)    bg=mul(bg,ma);
40         ma=mul(ma,ma);
41         p>>=1;
42     }
43     return bg;
44 }
45 int main()
46 {
47     int a,b,n;
48     while(scanf("%d%d%d",&a,&b,&n)&&(a!=0&&b!=0&&n!=0))
49     {
50         ma.m=a;ma.m=b;
51         ma.m=1;ma.m=0;
52         if(n<3)
53         {
54             printf("1n");
55             continue;
56         }
57         matrix ans=fast_martix_pow(ma,n-2);
58         printf("%dn",(ans.m+ans.m)%mod);
59     }
60     return 0;
61 }
``````

1005 Number Sequence（矩阵），hdu1005 Time
Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K
(Java/Others) Total Submission(s): 177761Accepted Submission(s):
44…

# DNA sequence

Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K
(Java/Others) Total Submission(s): 1505 Accepted Submission(s): 730

Problem Description The twenty-first century is a biology-technology
developing century. We know that a gene is made of DNA. The nucleotide
bases from which DNA is built are A(adenine), C(cytosine), G(guanine),
and T(thymine). Finding the longest common subsequence between
DNA/Protein sequences is one of the basic problems in modern
computational molecular biology. But this problem is a little different.
Given several DNA sequences, you are asked to make a shortest sequence
from them so that each of the given sequence is the subsequence of it.

For example, given “ACGT”,”ATGC”,”CGTT” and “CAGT”, you can make a
sequence in the following way. It is the shortest but may be not the
only one. Input The first line is the test case number t. Then t test cases
follow. In each case, the first line is an integer n ( 1<=n<=8 )
represents number of the DNA sequences. The following k lines contain
the k sequences, one per line. Assuming that the length of any sequence
is between 1 and 5.
Output For each test case, print a line containing the length of the
shortest sequence that can be made from these sequences.
Sample Input

``````1
4
ACGT
ATGC
CGTT
CAGT
``````

Sample Output

``````8
``````

Author LL
Source HDU 2006-12 Programming Contest
Recommend LL | We have carefully selected several similar problems for
you: 1667 1043 1813 1226 1401

``````#include
#include
#include
#include

using namespace std;

int n;
char ch;
int len,want;
char dir= {'A','C','G','T'};
int wei;//记录第i个序列正在使用第几个位置

int get_h()
{
int t=0;
for (int i=1; i<=n; i++)
{
t=max(t,len[i]-wei[i]);//得到当前情况下最长的未被匹配的长度
}
return t;
}

int IDA(int dep)
{
if(dep+get_h()>want)//当前长度+估测的长度比我想要的还大的话，就不必继续搜索
{//cout<<Max)
Max=len[i];
}
memset(wei,0,sizeof(wei));
want=Max;//从最长序列开始查找
while (1)
{
if (IDA(0))
{
break;
}
want++;
}
printf ("%dn",want);
}
return 0;
}
<
``````

1560 DNA sequence（IDA*） DNA sequence Time
Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K
(Java/Others) Total Submission(s): 1505 Accepted Submission(s):
730…

# DNA sequence

##### Total Submission(s) : 8 Accepted Submission(s) : 1

Problem Description The twenty-first century is a biology-technology
developing century. We know that a gene is made of DNA. The nucleotide
bases from which DNA is built are A(adenine), C(cytosine), G(guanine),
and T(thymine). Finding the longest common subsequence between
DNA/Protein sequences is one of the basic problems in modern
computational molecular biology. But this problem is a little different.
Given several DNA sequences, you are asked to make a shortest sequence
from them so that each of the given sequence is the subsequence of it.

For example, given ACGT,ATGC,CGTT and CAGT, you can make a sequence in
the following way. It is the shortest but may be not the only one. Input The first line is the test case number t. Then t test cases
follow. In each case, the first line is an integer n ( 1<=n<=8 )
represents number of the DNA sequences. The following k lines contain
the k sequences, one per line. Assuming that the length of any sequence
is between 1 and 5.
Output For each test case, print a line containing the length of the
shortest sequence that can be made from these sequences.
Sample Input

``````1
4
ACGT
ATGC
CGTT
CAGT
``````

Sample Output

``````8
``````

Author LL
Source HDU 2006-12 Programming Contest

IDA* 价值评估函数为最长剩余DNA数量

``````#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define inf 1<<30
#define LL long long
#define maxn 1<<24
using namespace std;
char str;//保存DNA
int l;
int t,n;
int tlen;
bool flag;

int get_h(int * a)  //估价函数
{
int ans=0;
for(int i=0; ilen) return ;//预估值小于最优估计值

if(len==0)  //找到序列
{
flag=true ;
return  ;
}

bool vis;
memset(vis,false ,sizeof(vis));
for(int i=0; i
``````

1560DNA sequence DNA sequence Time Limit :
15000/5000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other) Total
Submission(s) : 8 Accepted Submission(s) : 1 Problem Descrip…