题意:给你 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;
}
分享到:
相关推荐
hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...
hdu 1695 GCD(欧拉函数+容斥原理).docx
acm hdu as easy as a+b
【HDU 3993】田忌赛马 题解+勘误 题解这里就略写一下了,主要是勘误。 这道题是2011年之前的多校训练题,2020年的今天,我们一个集训队全部挂在上面了。最后在HDU看到了9年前的讨论区,才知道这题有如下问题: speed...
hdu2000-2014ac代码,虽然只有几道,但都是简单的
ACM题库,一些题目和答案,以及解题报告,传上来共享
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
HDU最全ac代码
hdu 一些简单题目 ac代码 大概100道
一个十分简单的程序,能够ac杭电hdu的第2050题,无注释,简单明了
杭电OnlineJudge 200-2099的解题报告
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
收集的部分HDOJ杭电ACM题的代码 大牛勿下 全是基础供初级acmer使用
hdu杭电所有题目按照ac数量排序,python分析
hdu2101AC代码
自己做的HDU ACM已经AC的题目
一款 HDU OJ 的自动刷题工具,搜索来源可选用 百度搜索 / 必应搜索,支持并行以及串行查找,祝早日刷上航电首页哦~ 使用 Python 编写,执行之前你需要在同目录下创建文件 aclog.txt ,然后粘贴进你目前已经 AC 的...
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
ACM hdu 代码大全3000例,hdu已经AC的3000例代码,部分代码有详细解析
Problem Description 话说,经过了漫长的一个多月,小明已经成长了许多,所以他改了一个名字叫“大明”。 这时他已经不是那个只会做100以内加法的那个“小明”了,现在他甚至会任意长度的正小数的加法。...