博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
hdu 2825 aC自动机+状压dp
阅读量:5833 次
发布时间:2019-06-18

本文共 4072 字,大约阅读时间需要 13 分钟。

Wireless Password

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 5640    Accepted Submission(s): 1785

Problem Description
Liyuan lives in a old apartment. One day, he suddenly found that there was a wireless network in the building. Liyuan did not know the password of the network, but he got some important information from his neighbor. He knew the password consists only of lowercase letters 'a'-'z', and he knew the length of the password. Furthermore, he got a magic word set, and his neighbor told him that the password included at least k words of the magic word set (the k words in the password possibly overlapping).
For instance, say that you know that the password is 3 characters long, and the magic word set includes 'she' and 'he'. Then the possible password is only 'she'.
Liyuan wants to know whether the information is enough to reduce the number of possible passwords. To answer this, please help him write a program that determines the number of possible passwords.
 

 

Input
There will be several data sets. Each data set will begin with a line with three integers n m k. n is the length of the password (1<=n<=25), m is the number of the words in the magic word set(0<=m<=10), and the number k denotes that the password included at least k words of the magic set. This is followed by m lines, each containing a word of the magic set, each word consists of between 1 and 10 lowercase letters 'a'-'z'. End of input will be marked by a line with n=0 m=0 k=0, which should not be processed.
 

 

Output
For each test case, please output the number of possible passwords MOD 20090717.
 
Sample Input
10 2 2
hello world
 
4 1 1
icpc
 
10 0 0
 
0 0 0
 
Sample Output
2
1
14195065
 
/*hdu 2825 aC自动机+状压dp给你m个子串,求长度为n的主串中至少出现k个子串的方案数首先通过AC自动机构建关系图. 然后用dp解决状态转移,需要知道用过哪些子串因为k比较小,我们直接转换成二进制来记录当前状态包含了哪些子串。用ed对各子串进行标记dp[i][j][t]就表示长度为i,当前位置上是j时,所包含子串的情况thhh-2016-04-24 17:13:36*/#include 
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;#define lson (i<<1)#define rson ((i<<1)|1)typedef unsigned long long ll;typedef unsigned int ul;const int mod = 20090717;const int INF = 0x3f3f3f3f;int tot;int dp[30][111][1<<10];struct Matrix{ int len; int ma[111][111]; Matrix() {}; Matrix(int L) { len = L; }};struct Tire{ int nex[110][26],fail[110],ed[110]; int root,L; int newnode() { for(int i = 0; i < 26; i++) nex[L][i] = -1; ed[L++] = 0; return L-1; } void ini() { L = 0,root = newnode(); } int cal(char ch) { if(ch == 'A') return 0; else if(ch == 'C') return 1; else if(ch == 'G') return 2; else if(ch == 'T') return 3; } void inser(char buf[],int id) { int len = strlen(buf); int now = root; for(int i = 0; i < len; i++) { int ta = buf[i] - 'a'; if(nex[now][ta] == -1) nex[now][ta] = newnode(); now = nex[now][ta]; } ed[now] |= (1<
q; fail[root] = root; for(int i = 0; i < 26; i++) if(nex[root][i] == -1) nex[root][i] = root; else { fail[nex[root][i]] = root; q.push(nex[root][i]); } while(!q.empty()) { int now = q.front(); q.pop(); if(ed[fail[now]]) ed[now] |= ed[fail[now]]; for(int i = 0; i < 26; i++) { if(nex[now][i] == -1) nex[now][i] = nex[fail[now]][i]; else { fail[nex[now][i]] = nex[fail[now]][i]; q.push(nex[now][i]); } } } } Matrix to_mat() { Matrix mat(L); memset(mat.ma,0,sizeof(mat.ma)); for(int i = 0; i < L; i++) { for(int j = 0; j < 4; j++) { if(!ed[nex[i][j]]) mat.ma[i][nex[i][j]] ++; } } return mat; }};//Matrix mat;Tire ac;char buf[22];void debug(){ Matrix t = ac.to_mat(); for(int i = 0; i < t.len; i++) { for(int j = 0; j < 26; j++) { printf("%d ",t.ma[i][ac.nex[i][j]]); } printf("\n"); }}int num[1<<10];int main(){ for(int i=0; i<(1<<10); i++) { num[i] = 0; for(int j = 0; j < 10; j++) if(i & (1<
0) for(int k = 0; k < 26; k++) { int nexi = i+1; int nexj = ac.nex[j][k]; int nexk = (t|ac.ed[nexj]); dp[nexi][nexj][nexk] = (dp[nexi][nexj][nexk] + dp[i][j][t])%mod; } } } } int ans = 0; for(int j = 0; j < (1<

  

转载于:https://www.cnblogs.com/Przz/p/5449315.html

你可能感兴趣的文章
C++_了解虚函数的概念
查看>>
全新jmeter视频已经上架
查看>>
Windows 8下如何删除无线配置文件
查看>>
oracle系列(五)高级DBA必知的Oracle的备份与恢复(全录收集)
查看>>
hp 服务器通过串口重定向功能的使用
查看>>
国外10大IT网站和博客网站
查看>>
android第十一期 - SmoothSwitchLibrary仿IOS切换Activity动画效果
查看>>
zabbix 批量web url监控
查看>>
MongoDB CookBook读书笔记之导入导出
查看>>
shell如何快速锁定所有账号
查看>>
HTML 5实现的手机摇一摇
查看>>
此博客不再发表对自己私事的看法
查看>>
导致Asp.Net站点重启的10个原因
查看>>
【PMP】Head First PMP 学习笔记 第一章 引言
查看>>
抓住云机遇编排工作 搞定复杂IT工作流
查看>>
MYSQL的longtext字段能放多少数据?
查看>>
MTK 平台上如何给 camera 添加一种 preview size
查看>>
云计算最大难处
查看>>
关于数据分析思路的4点心得
查看>>
Memcached安装与配置
查看>>