bzoj 1009: [HNOI2008] GT 시험(AC 자동기 + 매트릭스 최적화 dp)

1009: [HNOI2008]GT 시험
Time Limit: 1 Sec  
Memory Limit: 162 MB
Submit: 2794  
Solved: 1723
[ Submit][ Status][ Discuss]
Description
아신은 GT 시험에 지원할 준비를 하고 있는데, 수험표 번호는 N자리 X1X2...Xn(0<=Xi<=9), 그는 수험표 번호에 불길한 숫자가 나오는 것을 원하지 않는다.그의 불길한 수학 A1A2...Am(0<=Ai<=9)에는 M자리가 있는데, 나타나지 않는 것은 X1X2...Xn에 A1A2와 같은 단락이 없습니다.Am. A1과 X1은 0일 수 있습니다.
Input
첫 번째 행에 N, M, K. 를 입력하고 다음 행에 M 비트 수를 입력합니다.N<=10^9,M<=20,K<=1000
Output
아신은 불길한 숫자가 나타나지 않는 번호가 몇 가지가 있는지 알고 싶어한다. 출력 모드 K에서 나머지 결과를 얻는다.
Sample Input
4 3 100 111
Sample Output
81
HINT
Source
[ Submit][ Status][ Discuss]
문제풀이: 이 문제의 폭력 dp는 텍스트 생성기와 같다.
f[i][j]는 원수열의 i위가 트리의 J번째 노드와 일치한다는 것을 나타낸다.
그리고 최적화 매트릭스를 구축한다. 만약에 현재 노드가 합법적이고 그의 아들도 합법적이라면 그는 그의 아들을 밀어낼 수 있다. 그래서 최적화 매트릭스에서 A[I][CH[I][J]]=1.
그리고 A^N은 옮긴 결과입니다.
폭력DP에 의하면 첫 번째 단계는 0이라는 노드와 연결된 노드만 업데이트되는 것을 알 수 있기 때문에 초기 행렬은 1이다×tot의 01 행렬.
마지막으로 초기 행렬을 다시 사용하고 A를 곱하면 결과를 누적하면 답이 된다.

#include  
#include  
#include    
#include    
#include    
#include    
using namespace std;    
int n,m,p,a[1000],tot;    
int ch[200][26],fail[1003],isend[1000];    
int f[2][1000],cnt;    
int N;    
struct data    
{    
    int a[100][100];    
}e;    
void insert()    
{    
    int now=0;    
    for (int i=1;i<=m;i++)    
     {    
        if (!ch[now][a[i]])   ch[now][a[i]]=++tot;    
        now=ch[now][a[i]];    
     }    
    isend[now]=1;    
}    
void makefail()    
{    
    int now=0;    
    queue p;    
    for (int i=0;i<=9;i++)    
     if (ch[now][i])  p.push(ch[now][i]);    
    while (!p.empty())    
    {    
        int now=p.front(); p.pop();    
        for (int i=0;i<=9;i++)    
         {        
            if (!ch[now][i])    
             {    
                ch[now][i]=ch[fail[now]][i];    
                continue;    
             }    
            int x=ch[now][i];    
            fail[x]=ch[fail[now]][i];    
            if (isend[fail[x]])  isend[x]=1;    
            p.push(x);    
         }    
    }    
}    
void clear(data &x)    
{    
    for (int i=1;i<=N;i++)    
     for (int j=1;j<=N;j++)    
      x.a[i][j]=0;    
}    
void change(data &a,data b)    
{    
    for (int i=1;i<=N;i++)    
     for(int j=1;j<=N;j++)    
      a.a[i][j]=b.a[i][j];    
}    
data mul(data a,data b)    
{    
    data c;    
    for (int i=1;i<=N;i++)    
     for (int j=1;j<=N;j++)    
     {    
        c.a[i][j]=0;    
        for (int k=1;k<=N;k++)    
         c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j]%p)%p;    
     }    
    return c;    
}    
data pow(data num,int x)    
{    
    data ans; clear(ans);    
    for (int i=1;i<=N;i++) ans.a[i][i]=1;    
    data base; change(base,num);    
    while(x)    
    {    
        if (x&1)  ans=mul(ans,base);    
        x>>=1;    
        base=mul(base,base);    
    }    
    return ans;    
}    
void build()    
{    
    N=tot; clear(e);    
    for (int i=1;i<=tot;i++)    
     {    
        if (isend[i]) continue;    
        for (int j=0;j<=9;j++)    
         {    
            if (isend[ch[i][j]])  continue;    
            e.a[i][ch[i][j]]=1;    
         }    
     }    
}    
int main()    
{    
    scanf("%d%d%d",&n,&m,&p);    
    char s[30]; scanf("%s",s+1);    
    for (int i=1;i<=m;i++)     
     a[i]=s[i]-'0';    
    insert();      
    for (int i=0;i<=9;i++)  
	if (!ch[0][i])  
	   ch[0][i]=++tot;  
    makefail();    
    build();    
    data ans=pow(e,n-1);    
    for (int i=0;i<=tot;i++)   
      {
      	if (isend[i]) continue;
      	for (int j=0;j<=9;j++)
      	 f[1][ch[i][j]]+=(i==0);
      }
    int t[100]; int sum=0;    
    for (int j=1;j<=N;j++)    
    {    
        t[j]=0;    
        for (int k=1;k<=N;k++)    
         t[j]=(t[j]+f[1][k]*ans.a[k][j]%p)%p;    
        sum=(sum+t[j])%p;    
    }    
    printf("%d
",sum);    
}