hdu 2243 의 AC 자동 동기 + 매트릭스 곱셈

대학원 진학 길이 막막 하 다 -- 단어 콤플렉스
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2789 Accepted Submission(s): 782
Problem Description
단 어 를 외 우 는 것 은 시종 영 어 를 복습 하 는 중요 한 부분 이다.3 년 간 대학 생활 을 등한시 한 뒤 릴 도 드디어 단 어 를 외우 기 시작 했다.
어느 날, 릴 은 어떤 단어 책 에서 어근 에 따라 단 어 를 외 우 는 방법 을 보 았 다.예 를 들 어 'ab' 는 단어 앞 에 놓 으 면 '반대로 나 빠 지고 떠 나' 등 을 나타 낸다.
그래서 릴 은 N 개의 어근 을 외 웠 다 면 이 어근 들 이 단어 에 나 오지 않 았 을 까 하 는 생각 이 들 었 다.더 정확 한 설명 은 길이 가 L 을 초과 하지 않 고 소문 자로 만 구성 되 어 있 으 며 적어도 하나의 어근 을 포함 하 는 단 어 는 모두 몇 개 일 수 있 습 니까?여기 서 는 단어 가 실제 적 인 의미 가 있 는 지 없 는 지 를 고려 하지 않 는 다.
예 를 들 어 모두 2 개의 어근 aa 와 ab 가 있 으 면 104 개의 길이 가 3 을 초과 하지 않 는 단어 가 존재 할 수 있 습 니 다. 각각
(2 개) aa, ab,
(26 개) aaa, aab, aac... aaz,
(26 개) aba, abb, abc... abz,
(25 개) baa, caa, daa... zaa,
(25 개) bab, cab, dab... zab.
이것 은 아주 작은 상황 일 뿐이다.다른 복잡 한 상황 에 대해 서 는 릴 이 셀 수 없 으 니 지금 도와 주세요.

Input
이 문 제 는 여러 그룹의 데 이 터 를 포함 하고 있 습 니 다. 파일 이 끝 날 때 까지 처리 하 십시오.
각 조 의 데이터 가 두 줄 을 차지한다.
첫 줄 에는 두 개의 정수 N 과 L 이 있다.(0 두 번 째 줄 에는 N 개의 어근 이 있 고 각 어근 은 소문 자로 만 구성 되 며 길 이 는 5 를 초과 하지 않 습 니 다. 두 어근 사이 에 하나의 빈 칸 으로 구 분 됩 니 다.

Output
각 그룹의 데이터 에 대해 서 는 한 줄 에 가능 한 단어 수 를 출력 하 십시오.
결과 가 매우 클 수 있 기 때문에 단어 총수 모드 2 ^ 64 의 값 만 출력 해 야 합 니 다.

Sample Input

 
   
     2 3 aa ab 1 2 a

Sample Output

 
   
     104 52

Author

linle

Recommend

lcy

这道题从上午搞到现在终于是用两种方法搞完了

在这里想说一句，输入的n,l其中l要用到64位，因为后面算26^1+26^2+...+26^l或者A^1+A^2+A^3+...+A^l时要用到(l+1)/2进行二分快速幂，而l+1可能会超int,网上很多都没说清楚

第二个就是求26^1+26^2+...+26^l或者A^1+A^2+A^3+...+A^l都可以用二分进行快速幂或直接进行矩阵快速幂，在这里我两种方法都写了

第三个就是计算26^1+26^2+...+26^l不要用等比公式变成(26^(l+1)-26)/25去进行快速幂计算，这样会出错，至于为什么出错自己调试调试就知道了

第四个就是题目中说结果可能很大需要去mod 2^64,在这里直接定义变量unsigned __int64,这样超出的就自动截断了，相当于mod

分析+题解请看代码

第一种方法：用二分矩阵快速幂求A^1+A^2+...+A^l

/*
  :    poj2778          n             
        ，   poj2778    
         <=n    -        
 26^1+26^2+26^3+...+26^n-(A^1+A^2+A^3+...+A^n);//A     ,                 
26^1+...+26^n        h         ,A^1+...+A^n                :
|1 26| |Sn  | |Sn+1    |
|0 26|*|26^n|=|26^(n+1)|;//Sn=26^1+26^2+...+26^n

|A 1| |Sn| |Sn+1|
|0 1|*| A|=|A   |;//Sn=A+A^2+A^3+...+A^n

  :|A 1|
     |0 1|
  n  |S0|    ,           
		 |A | 
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define INF 99999999
using namespace std;

const int MAX=30+10;
//unsigned __int64 mod=1ll<<64;
unsigned __int64 array[MAX][MAX],sum[MAX][MAX],temp[MAX][MAX],ans[MAX][MAX];
__int64 l;
int size,n; 
char s[10];

struct TrieNode{
	bool mark;//       
	int id;//      
	TrieNode *fail,*next[26]; 
}*root,Node[MAX];

TrieNode *New_TrieNode(){
	memset(&Node[size],0,sizeof(TrieNode));
	Node[size].id=size;
	return &Node[size++];
}

void InsertNode(char *a){//     
	TrieNode *p=root;
	while(*a){
		if(!p->next[(*a)-'a'])p->next[(*a)-'a']=New_TrieNode();
		p=p->next[(*a)-'a'];
		++a;
	}
	p->mark=true;
}

void Build_AC(){//  AC          array
	memset(array,0,sizeof array); 
	TrieNode *p,*next;
	queueq;
	q.push(root);
	while(!q.empty()){
		p=q.front();
		q.pop();
		for(int i=0;i<26;++i){
			if(p->next[i]){
				next=p->fail;
				while(next && !next->next[i])next=next->fail;
				p->next[i]->fail=next?next->next[i]:root;
				if(p->next[i]->fail->mark)p->next[i]->mark=true;//         ,acg,ac
				q.push(p->next[i]); 
			}else p->next[i]=(p == root)?root:p->fail->next[i];// p->id       p->fail->next[i]  
			if(!p->next[i]->mark)++array[p->id][p->next[i]->id];//             ,      
		}
	}
}

void MatrixInit(unsigned __int64 a[MAX][MAX],bool flag){//      
	for(int i=0;i>=1;
	}
}

void MatrixSum(__int64 k){//A^1+A^2+A^3+...+A^n
	if(k == 1){MatrixInit(ans,1);return;}
	MatrixSum(k/2);
	MatrixPow((k+1)/2);//     k+1, k+1    int,  k l  64  
	if(k&1){//A+(A+A^m)*(A^1+A^2+...);//m=(k+1)/2
		MatrixInit(temp,1);//temp=A;
		MatrixAdd(sum,temp);//sum=sum+temp=A^m+A
		MatrixMult(ans,sum);//ans=ans*sum=(A^1+A^2+...)*(A^m+A)
		MatrixAdd(ans,temp);//ans=ans+temp=ans+A=A^1+A^2+...)*(A^m+A)
	}else{//(1+A^m)*(A^1+A^2+...);//m=(k+1)/2
		MatrixInit(temp,0);//temp=1
		MatrixAdd(temp,sum);//temp=temp+sum=1+A^m
		MatrixMult(ans,temp);//ans=ans*temp=(A^1+A^2+...)*(1+A^m)
	}
}

int main(){
	while(scanf("%d%I64d",&n,&l)!=EOF){
		size=2;
		array[0][0]=1,array[0][1]=26;
		array[1][0]=0,array[1][1]=26;
		MatrixPow(l);// 26^1+26^2+...+26^l
		unsigned __int64 all=sum[0][1];
		printf("%I64u
",all);
		size=0;
		root=New_TrieNode();
		for(int i=0;i

두 번 째 방법: 행렬 을 포함 하 는 행렬 로 빠 른 속도 로 A ^ 1 + A ^ 2 + A ^ 3 +.

/*
  :    poj2778          n             
        ，   poj2778    
         <=n    -        
 26^1+26^2+26^3+...+26^n-(A^1+A^2+A^3+...+A^n);//A     ,                 
26^1+...+26^n        h         ,A^1+...+A^n                :
|1 26| |Sn  | |Sn+1    |
|0 26|*|26^n|=|26^(n+1)|;//Sn=26^1+26^2+...+26^n

|A 1| |Sn| |Sn+1|
|0 1|*| A|=|A   |;//Sn=A+A^2+A^3+...+A^n

  :|A 1|
     |0 1|
  n  |S0|    ,           
		 |A | 
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define INF 99999999
using namespace std;

const int MAX=30+10;
//unsigned __int64 mod=1ll<<64;
unsigned __int64 array[MAX][MAX],sum[2][2][MAX][MAX],temp[2][2][MAX][MAX];
int size,n;
__int64 l;
char s[10];

struct TrieNode{
	bool mark;//       
	int id;//      
	TrieNode *fail,*next[26]; 
}*root,Node[MAX];

TrieNode *New_TrieNode(){
	memset(&Node[size],0,sizeof(TrieNode));
	Node[size].id=size;
	return &Node[size++];
}

void InsertNode(char *a){//     
	TrieNode *p=root;
	while(*a){
		if(!p->next[(*a)-'a'])p->next[(*a)-'a']=New_TrieNode();
		p=p->next[(*a)-'a'];
		++a;
	}
	p->mark=true;
}

void Build_AC(){//  AC          array
	memset(array,0,sizeof array); 
	TrieNode *p,*next;
	queueq;
	q.push(root);
	while(!q.empty()){
		p=q.front();
		q.pop();
		for(int i=0;i<26;++i){
			if(p->next[i]){
				next=p->fail;
				while(next && !next->next[i])next=next->fail;
				p->next[i]->fail=next?next->next[i]:root;
				if(p->next[i]->fail->mark)p->next[i]->mark=true;//         ,acg,ac
				q.push(p->next[i]); 
			}else p->next[i]=(p == root)?root:p->fail->next[i];// p->id       p->fail->next[i]  
			if(!p->next[i]->mark)++array[p->id][p->next[i]->id];//             ,      
		}
	}
}

void MatrixInit(unsigned __int64 A[2][2][MAX][MAX],bool flag){//      
	for(int a=0;a<2;++a){
		for(int b=0;b<2;++b){
			for(int i=0;i>=1;
	}
}

unsigned __int64 FastPow(unsigned __int64 a,int k){
	unsigned __int64 ans=1;
	while(k){
		if(k&1)ans=ans*a;
		a=a*a;
		k>>=1;
	}
	return ans;
}

unsigned __int64 FastSum(__int64 k){
	if(k == 1)return 26;
	unsigned __int64 ans=FastSum(k/2);
	unsigned __int64 a=FastPow(26ull,(k+1)/2);//     k+1, k+1    int,k  64  
	if(k&1)return 26+(26+a)*ans;//26+(26+26^m)*(26^1+26^2+...),m=(k+1)/2
	else return (1+a)*ans;//(1+26^m)*(26^1+26^2+...),m=(k+1)/2
}

int main(){
	while(scanf("%d%I64d",&n,&l)!=EOF){
		size=0;
		root=New_TrieNode();
		for(int i=0;i

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[AC 자동 동기] hdoj 3065: 바이러스 침입 지속 중

대체로 제목: n 개의 패턴 문자열, 하나의 텍스트 문자열 을 보 여 줍 니 다. 각각 텍스트 문자열 이 패턴 문자열 에 나타 나 는 횟수 를 구 합 니 다. 대체적인 사고방식: 기본 적 인 AC 자동 동 기 는 일...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

hdu 2243 의 AC 자동 동기 + 매트릭스 곱셈

좋은 웹페이지 즐겨찾기