hdu 2825 Wireless Password(ac 자동기 + 상압 dp)
m개의 열을 주십시오. 현재 n개의 자모의 자구에는 적어도 p개의 m 집합 중의 열을 포함해야 합니다.몇 가지 방법이 있느냐고 물었다.
문제 풀이:
kuangbin은 ac자동기 상태 이동도 뭐라고 하는데 잘 몰라요.하지만 이것을 버리고 생각해도 할 수 있다.우리는 ac자동기에서 dp는 반드시 이런 상태를 설정해야 한다. dp[i][j]는 i보를 갔고 끝은 j노드이다. 그러나 이렇게 하면 몇 m 집합 중의 열을 얻을 수 없다. 이 유사한 배열 조합을 분석한 결과 이런 계수 문제를 실현하려면 상압 dp만 있을 뿐이다. 그러면 우리는 1차원 dp[i][j][s]s를 많이 설정하면 m집합 중의 열을 얻는 상태를 나타낸다.마지막으로 상태에서 p보다 큰 1개의 답을 얻으면 된다.
#include<iostream>
#include<math.h>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<map>
#include<set>
using namespace std;
#define B(x) (1<<(x))
typedef long long ll;
const int oo=0x3f3f3f3f;
const ll OO=1LL<<61;
const ll MOD=20090717;
const int maxn=1005;
const int SIZE=110;
char str[maxn];
int dp[27][SIZE][B(10)+5];
int num[B(10)+5];
struct AC
{
int next[SIZE][26],fail[SIZE],end[SIZE],Q[SIZE*26];
int root,cnt;
void Init()
{
cnt=0;
root=newNode();
}
int newNode()
{
for(int i=0;i<26;i++)
next[cnt][i]=-1;
end[cnt++]=0;
return cnt-1;
}
void Insert(char buff[],int id)
{
int now=root;
int len=strlen(buff);
for(int i=0,k;i<len;i++)
{
k=buff[i]-'a';
if(next[now][k]==-1)
next[now][k]=newNode();
now=next[now][k];
}
end[now]|=B(id);///
}
void build()
{
fail[root]=root;
int front,rear;
front=rear=0;
int now=root;
for(int i=0;i<26;i++)
{
if(next[now][i]==-1)
next[now][i]=root;
else
{
fail[next[now][i]]=root;
Q[rear++]=next[now][i];
}
}
while(front<rear)
{
now=Q[front++];
end[now]|=end[fail[now]];///
for(int i=0;i<26;i++)
{
if(next[now][i]==-1)
next[now][i]=next[fail[now]][i];
else
{
fail[next[now][i]]=next[fail[now]][i];
Q[rear++]=next[now][i];
}
}
}
}
void add(int& a,int b)
{
a=(a+b)%MOD;
}
int DP(int n,int m,int p)
{
int full=B(m)-1;
//memset(dp,0,sizeof dp);
for(int i=0;i<=n;i++)
for(int j=0;j<cnt;j++)
for(int s=0;s<=full;s++)
dp[i][j][s]=0;
dp[0][0][0]=1;
for(int i=0;i<n;i++)
{
for(int j=0;j<cnt;j++)
{
for(int s=0;s<=full;s++)
if(dp[i][j][s])
{
for(int t=0;t<26;t++)
{
int k=next[j][t];
int st=s|end[k];
add(dp[i+1][k][st],dp[i][j][s]);
}
}
}
}
int ans=0;
for(int s=0;s<=full;s++)
if(num[s]>=p)
for(int i=0;i<cnt;i++)
add(ans,dp[n][i][s]);
return ans;
}
};
AC ac;
void Init()
{
int S=B(10);
for(int i=0;i<S;i++)
{
num[i]=0;
for(int j=0;j<10;j++)
if(i&B(j))
num[i]++;
}
}
int main()
{
Init();
int n,m,p;
while(scanf("%d %d %d",&n,&m,&p)!=EOF)
{
if(n==0&&m==0&&p==0)break;
ac.Init();
for(int i=0;i<m;i++)
{
scanf("%s",str);
ac.Insert(str,i);
}
ac.build();
cout<<ac.DP(n,m,p)<<endl;
}
return 0;
}
/**
10 2 2
hello
world
4 1 1
icpc
10 0 0
0 0 0
*/
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.