[HDU2825] Wireless Password, AC 로봇 + 상태 압축 DP

전송문은 앞에 쓰여 있다. 여전히 독이 있는 HDU인데 문제를 한참 동안 읽어도 모르겠다. 자동기의 정통함은 기약할 수 없을 것 같다!사고방식: 제목 - m개에 주어진 직렬(같을 수 있음)을 정하고 길이가 n인 새 직렬을 구성하도록 요구한다. 새 직렬에 최소한 k개의 주어진 직렬(번호 중복 계산)을 포함하고 새 직렬을 구성하는 방안의 수를 요구한다. 모든 문자는'a'-'z'(데이터 범위가 이렇게 작은 것을 보면 고차원 DP, 상압 DP와 네트워크 흐름)을 생각해서 트리를 만들고 fail 지침을 세운 다음에 자동기에서 DP를 한다.f[i][j][p]는 DP가 길이가 i인 새 직렬에 이르렀다는 것을 의미한다. 이때 자동기기의 노드는 j이고 p는 01이진법으로 m개의 주어진 직렬의 선택 상황을 나타낸다. 선택하면 1이고 선택하지 않으면 0이다(따라서 트리를 만들어서 m개의 직렬에 주는 표호는 1<(id-1)이지 id가 아니다).f[i][j][p]가 확장할 수 있는 상태는 f[i+1][next][p|num[next]]next는 자동기기의 노드 j가 옮길 수 있는 모든 번호(없으면 fail 노드로 돌아가서 찾고fail을 만들 때 이 일을 처리한다)이다. 마지막으로 우리가 원하는 답은 f[n][i][j]이다. i는 자동기기의 임의의 노드이고 j는 2진법 아래에서 요구>=k개 1이다. 그러나 j의 범위는 0-1023이다.그래서 0-1023 모든 수의 2진법 1의 수량을 미리 처리하면 됩니다. 주의: 초기화는 여전히 주의해야 합니다. 그리고 어떤 것을 삭제해야 하는지, 어떤 것이memset을 사용하지 않을 수 있는지... 코드:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define mod 20090717
using namespace std;
int n,m,k,root=1,tot; 
char s[15];
int trie[110][26],num[4000],f[30][110][1030],fail[4000],sum[1025];
queue<int>q;
void insert(char s[],int id)
{
    int now=root;
    for (int i=0;i<strlen(s);i++)
    {
        if (!trie[now][s[i]-'a']) trie[now][s[i]-'a']=++tot;
        now=trie[now][s[i]-'a'];
    }
    num[now]|=(1<<id-1);
}
void build()
{
    int now,tmp;
    q.push(root);
    while (!q.empty())
    {
        now=q.front();
        q.pop();
        num[now]|=num[fail[now]];
        for(int i=0;i<26;i++)
        if (trie[now][i])
        {
            tmp=fail[now];
            while (tmp&&!trie[tmp][i]) tmp=fail[tmp];
            if (now!=root&&tmp) fail[trie[now][i]]=trie[tmp][i];
            else fail[trie[now][i]]=root;
            q.push(trie[now][i]);
        }
        else
        {
            if (now==root) trie[now][i]=root;
            else trie[now][i]=trie[fail[now]][i];
        }
    }
}
int main()
{
    for (int i=0;i<1024;i++)
    {
        int t=i;
        while (t)
        {
            if (t&1) sum[i]++;
            t>>=1;
        }
    }
    int x,y,z;
    scanf("%d%d%d",&n,&m,&k);
    while (n||m||k)
    {
        int ans=0;tot=1;
        memset(trie,0,sizeof(trie));
        memset(num,0,sizeof(num));
        for (int i=1;i<=m;i++)
            scanf("%s",s),
            insert(s,i);
        for (int i=0;i<=tot;i++) fail[i]=0;
        build();
        for (int i=0;i<=n;i++)
            for (int j=0;j<=tot;j++)
                for (int p=0;p<(1<<m);p++) f[i][j][p]=0;
        f[0][1][0]=1;
        bool now=0;
        for (int i=0;i<n;i++)
            for (int j=1;j<=tot;j++)
                for (int p=0;p<(1<<m);p++)
                if (f[i][j][p])
                    for (int l=0;l<26;l++)
                        x=i+1,y=trie[j][l],z=num[y]|p,
                        f[x][y][z]=(f[x][y][z]+f[i][j][p])%mod;
        for (int j=0;j<(1<<m);j++)
            if (sum[j]>=k)
                for (int i=1;i<=tot;i++)
                    ans=(ans+f[n][i][j])%mod;
        printf("%d
",ans);
        scanf("%d%d%d",&n,&m,&k);
    }
}