2778.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Problem Id:2778  User Id:fzk 
Memory:2036K  Time:123MS
Language:C++  Result:Accepted

Source 

#include "stdio.h"
#include "memory.h"
#include "string.h"
#include "algorithm"
#include "functional"
using namespace std;

const int CHAR_NUM = 4;
const int MAXSIZE = 1000;
const int PATTERN = 100;

struct pretree {
	pretree *ch[CHAR_NUM], *s;
	int ok;
}pret[ MAXSIZE ], *prev[MAXSIZE];

pair< int, char* > pn[PATTERN];

int use_node, pn_num;
int index[256];

pretree *proot;

int get_index( char c ) {
	return index[c];
}

pretree* find_s( pretree *t, char c ) {
	int k = get_index(c);
	while( t!=proot && !t->ch[ k ] )
		t = t->s;
	if( t->ch[ k ] )
		t = t->ch[ k ];
	return t;
}

pretree* new_node( ) {
	memset( pret[use_node].ch, 0, sizeof(pret[0].ch) );
	return pret+( use_node++ );
}

pretree* insert( pretree *p, char c, int end ) {
	int k = get_index( c );
	
	pretree* q = p->ch[ k ];
	if( !q ) {
		q = new_node( );
		q->s = find_s( p->s, c );
		q->ok = q->s->ok;
		p->ch[k] = q;
	}

	if( end >= 0 )
		q->ok = end;
	return q;
}

void create( char *w[], int m ) {
	int i, j;
	for( i=0; i<m; i++ ) {
		pn[i].first = strlen( w[i] );
		pn[i].second = w[i];
	}
	sort( pn, pn+m, greater< pair< int, char* > >() );

	use_node = 0;
	proot = new_node( );
	proot->ok = -1;
	proot->s = proot;	//! proot->s points to itself.

	for( i=0; i<m; i++ )
		prev[i] = proot;

	for( j=0; m; j++ ) {
		for( i=0; i<m && pn[i].second[j]; i++ )
			prev[i] = insert( prev[i], pn[i].second[j], pn[i].second[j+1]?-1:i );
		m = i;
	}

}
//////////////////////////////////////////////////////////////////////////

char ws[100][100];
char *wp[100];
int id[100];
const int mod = 100000;
int a[50][100][100], (*a0)[100] = a[0], (*ans)[100] = a[49], (*temp)[100] = a[48];

int n;

const char chars[] = "AGCT";

void mul( int (*A)[100], int (*B)[100], int (*C)[100] ) {
	int i, j, k;
	__int64 temp;
	for( i=0; i<n; i++ )
	for( j=0; j<n; j++ ) {
		temp = 0;
		for( k=0; k<n; k++ ) {
			temp += (__int64)A[i][k]*B[k][j];
			if( temp > ( (__int64)1<<45 ) )
				temp %= mod;
		}
		C[i][j] = int(temp%mod);
	}
}
				

int main( ) {
	int i, m, l, j, k, answer;
	__int64 s;

	index['A'] = 0;
	index['G'] = 1;
	index['C'] = 2;
	index['T'] = 3;

	memset( a, 0, sizeof a );

	scanf( "%d %d", &m, &l );
	
	for( i=0; i<m; i++ ) {
		scanf( "%s", ws[i] );
		if( strlen( ws[i] ) > l)
			i--, m--;
		else
			wp[i] = ws[i];
	}

	create( wp, m );
	for( i=0,n=0; i<use_node; i++ )
		if( pret[i].ok == -1 ) {
			id[i] = n++;
		}
	
	
	for( i=0; i<use_node; i++ ) 
	if( pret[i].ok == -1 ) {
		for( k=0; k<4; k++ ) {
			j = find_s( pret+i, chars[k] ) - pret;
			if( pret[j].ok == -1 )
				a0[id[i]][id[j]]++;
		}
	}


	for( i=0, s=1; s<=l; i++, s<<=1 )
		mul( a[i], a[i], a[i+1] );
	memset( ans, 0, sizeof ans );
	for( i=0; i<n; i++ )
		ans[i][i] = 1;

	for( i=0; l; i++, l>>=1 )
	if( l&1 ) {
		mul( ans, a[i], temp );
		swap( ans, temp );
	}

	answer = 0;
	for( i=0; i<n; i++ )
		answer = (answer+ans[0][i])%mod;
	printf( "%d\n", answer );

	return 0;
}