`
darren_nizna
  • 浏览: 72780 次
  • 性别: Icon_minigender_1
  • 来自: 长沙
社区版块
存档分类
最新评论

[HDU][2243][单词情结][AC自动机 + 矩阵乘法]

J# 
阅读更多

题意:给你 n 个单词,求出满足以下条件的单词个数:长度不大于 L 且单词中至少包含一个子串为前面 n 个单词中任意一个。先求出所有单词的数量 26^1+ 26^2+ ... + 26^L,可以用矩阵乘法求出,也可用逆元的方法。然后求出所有不包含 n 个单词的串的数量,这个求法和 pku 2778 相同,只是这里要求出所有长度不大于 L 的字符串数量和,方法参考 pku 3233。两者相减就是答案。对那个 2^64 求余,用unsigned __int64 存储的数据,相乘溢出后剩下的结果,就直接是对2^64取模的结果。

 

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

typedef unsigned __int64 ULL;
int N, L;

struct Node{
	int next[26];
	int fail, flag;
	void init(){
		for( int i= 0; i< 26; ++i ) next[i]= 0;
		fail= -1; flag= 0;
	}
}tb[100];

char str[100];
int cnt= 0;
ULL mat[100][100], A[100][100], B[100][100];

void insert( char*s ){
	int rt= 0;
	while( *s ){
		int t= *s- 'a';
		
		if( tb[rt].next[t]== 0 ){
			tb[++cnt].init();
			tb[rt].next[t]= cnt;
		}
		rt= tb[rt].next[t]; s++;
	}
	tb[rt].flag= 1;
}

void bfs(){
	int que[1000], head= 0, tail= 0;  que[0]= 0;
	int p, q;
	
	while( head<= tail ){
		int now= que[head++];
		
		for( int t= 0; t< 26; ++t )
		if( tb[now].next[t]!= 0 ){
			p= tb[now].next[t]; q= tb[now].fail;
			
			while( q!= -1 && !tb[q].next[t] ) q= tb[q].fail;
			if( q== -1 ) tb[p].fail= 0;
			else {
				tb[p].fail= tb[q].next[t];
				tb[p].flag|= tb[ tb[p].fail ].flag;
			}
			que[++tail]= p;
		}
		else{
			q= tb[now].fail;
			
			while( q!= -1 && !tb[q].next[t] ) q= tb[q].fail;
			if( q== -1 ) tb[now].next[t]= 0;
			else tb[now].next[t]= tb[q].next[t];
		}
	}
}

void inline mult( ULL x[100][100], ULL y[100][100], int len ){
	ULL z[100][100];
	
	for( int i= 0; i< len; ++i )
	for( int j= 0; j< len; ++j ){
		z[i][j]= 0;
		
		for( int k= 0; k< len; ++k )
		z[i][j]+= x[i][k]* y[k][j];
	}
	
	for( int i= 0; i< len; ++i )
	for( int j= 0; j< len; ++j )
	y[i][j]= z[i][j];
}

ULL getNum(){
	for( int i= 0; i< 100; ++i )
	for( int j= 0; j< 100; ++j ){
		mat[i][j]= 0; A[i][j]= 0; B[i][j]= 0; }
		
	for( int i= 0; i< 100; ++i ) B[i][i]= 1;
	
	for( int i= 0; i<= cnt; ++i )
	if( !tb[i].flag )
	for( int t= 0; t< 26; ++t )
	if( !tb[ tb[i].next[t] ].flag )
	mat[i][ tb[i].next[t] ]++;

	for( int i= 0; i< cnt; ++i ){
		A[i][i]= 1; A[i+cnt][i]= 1;
		
		for( int j= 0; j< cnt; ++j )
		A[i+ cnt][j+ cnt]= mat[i][j];
	}
	
	int p= L;
	while( p ){
		if( p& 1 ) mult( A, B, cnt<<1 );
		mult( A, A, cnt<<1 ); p>>= 1;
	}

	for( int i= 0; i< cnt; ++i )
	for( int j= 0; j< cnt; ++j ) B[i][j]= B[i+cnt][j];
	
	mult( B, mat, cnt );
	
	ULL res= 0;
	for( int i= 0; i< cnt; ++i )
	res+= mat[0][i];
	
	return res;
}

ULL totNum(){
	mat[0][0]= 1; mat[0][1]= 0;
	mat[1][0]= 26; mat[1][1]= 26;
	
	A[0][0]= 1; A[0][1]= 0;
	A[1][0]= 0; A[1][1]= 1;
	
	int p= L- 1;
	while( p ){
		if( p& 1 ) mult( mat, A, 2 );
		mult( mat, mat, 2 ); p>>= 1;
	}
	
	ULL res= 0;
	res= A[0][0]* 26+ A[1][0]* 26;
	
	return res;
}

int main(){
	while( scanf("%d%d",&N, &L)!= EOF ){
		tb[0].init(); cnt= 0;
		
		for( int i= 0; i< N; ++i ){
			scanf("%s", str );
			insert( str );
		}
		bfs();
		
		ULL ans= totNum()- getNum();
		if( ans< 0 ) ans= ans+ (1llu<<63)+ (1llu<<63);
		
		printf("%I64u\n", ans );
	}
	
	return 0;
}

 

1
0
分享到:
评论

相关推荐

    hdu 3341(ac自动机+状态压缩)

    hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...

    hdu 1695 GCD(欧拉函数+容斥原理).docx

    "hdu 1695 GCD(欧拉函数+容斥原理)" 题目大意是:给定 a, b, c, d, k,找到一队 x, y,满足 g(x, y) = k,且 x ∈ [1, b], y ∈ [1, d],问有多少对符合要求的 (x, y)。 思路是:gcd(x, y) == k 解释 x, y 都能...

    HDU ACM as easy as a+b

    - **HDU** 指的是“杭州电子科技大学”(Hangzhou Dianzi University),这所大学在ACM国际大学生程序设计竞赛中有着优异的表现。 - **ACM** 是指“Association for Computing Machinery”,即计算机协会,而在此处...

    HDU+2000-2099+解题报告

    例如背包问题、最长公共子序列、矩阵链乘法等。 3. **图论**:包括最短路径算法(Dijkstra、Floyd-Warshall、Bellman-Ford)、最小生成树(Prim、Kruskal)、拓扑排序等。 4. **字符串处理**:如KMP算法、Manacher...

    hdu 300+ AC 代码

    HDU 300+ AC 代码集合是一个包含超过300个已通过验证的算法解决方案的资源,这些代码主要用于解决各类计算机编程竞赛中的问题。这些竞赛通常由杭州电子科技大学(HDU)主办,旨在提升参赛者的算法设计、编程和问题...

    HDU+2000-2099+解题报告.zip

    1. **动态规划**:动态规划是一种用于解决最优化问题的常用方法,例如背包问题、最长公共子序列、矩阵链乘法等。解题报告会解释如何定义状态、设计状态转移方程,并给出具体代码实现。 2. **图论算法**:包括最短...

    杭电HDU2050题的ac程序

    一个十分简单的程序,能够ac杭电hdu的第2050题,无注释,简单明了

    HDU最全ac代码

    "HDU最全ac代码"这个压缩包很可能是包含了在HDU平台上解题通过的完整源代码集合,旨在帮助学习者理解和掌握各种算法,提升编程解决问题的能力。 首先,我们来了解一下ACM/ICPC比赛。这是一项全球性的编程竞赛,参赛...

    hdu2000-2014ac代码

    "AC"代表"Accepted",意味着提交的代码已经被评测系统接受,成功通过了所有测试用例。这个压缩包中的代码可能是用户在解决HDU平台上的编程题目时编写的,时间跨度从2000年至2014年。 从描述中我们可以推测,这个...

    【HDU 3993】田忌赛马 题解+勘误

    【田忌赛马】是一道源自古代中国历史的著名策略问题,被转化为计算机科学中的算法题目,出现在HDU(杭州电子科技大学在线评测系统)的3993号问题中。该题目的主要目的是通过编程来解决如何在不确定的对手策略下,...

    hdu 的2072,2084,2082,1170,ac代码

    这些题目包括HDU 2072、2084、2082和1170,每道题目都有其特定的解决思路和代码实现,而AC代码正是这些思路得以实现的证明。 首先,HDU 2072题要求我们处理字符串,并进行单词的计数与去重。在编程实践中,字符串...

    hdu 一些简单题目 ac代码

    "AC"是编程比赛中常用的术语,代表"Accepted",意味着你的代码已经正确解决了题目所提出的问题,并通过了所有测试用例。 从提供的文件名来看,这些是针对HDU题目的C++源代码文件,具体题目编号包括1007、10071、...

    HDU刷题地图+精选详细笔记

    本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!

    HDU ACM HDOJ 部分基础题AC代码

    【知识点详解】 本题是基于ACM(国际大学生程序设计竞赛)的一道基础题目,主要涉及大整数的加法运算。ACM竞赛中的题目往往需要程序员具备快速解决问题的能力,对于算法的理解和实现要求较高。...

    HDU_2010.rar_hdu 2010_hdu 20_hdu acm20

    【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...

    ACM hdu 线段树题目+源代码

    ACM hdu 线段树题目+源代码 线段树是一种非常重要的数据结构,它广泛应用于算法竞赛和实际编程中。今天,我们将通过 ACM hdu 的几个题目来学习和掌握线段树的基本概念和应用。 线段树的基本概念 线段树是一种...

    hdu.rar_hdu

    HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在...

    HDU题目java实现

    9. **动态规划**:这是一种优化策略,通过构建状态转移方程来求解问题,例如背包问题、最长公共子序列、矩阵链乘法等。 10. **回溯法**:在解决组合优化问题和逻辑推理问题时常用,如八皇后问题、数独求解等。 11....

    Hdu1000—2169部分代码

    6. **字符串处理**:KMP匹配、Z算法、后缀数组、AC自动机等。 通过分析和理解这些代码,你可以提升自己的算法思维,学习如何高效地解决问题,这对于参加ACM竞赛或者日常的编程工作都非常有益。同时,也可以借鉴代码...

    HDU 自动 AC 机(Python)

    一款 HDU OJ 的自动刷题工具,搜索来源可选用 百度搜索 / 必应搜索,支持并行以及串行查找,祝早日刷上航电首页哦~ 使用 Python 编写,执行之前你需要在同目录下创建文件 aclog.txt ,然后粘贴进你目前已经 AC 的...

Global site tag (gtag.js) - Google Analytics