空罐Cans

空罐Cans

题意：中文题，不多说了

用dp[i][j][k]表示第i天，长度为j的，走到了k节点罐子有几个，第i+1天的时候，罐子分裂，就加一个儿子。基因缩短，看当前节点的深度是否小于j-1，如果小于，就走到k的fail节点，否则还是在k节点。状态我是用广搜搜出来的。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std ;

const int maxn = 1555 ;
const int mod = 10007 ;
int dp[333][111][maxn] ;
bool vis[333][111][maxn] ;

struct Point
{
	int d , l , p ;
} ;

struct Que
{
	int tail , head ;
	Point q[1000005] ;
	void init ()
	{
		head = 1 , tail = 0 ;
	}
	bool empty ()
	{
		return head > tail ;
	}
	Point front ()
	{
		return q[head] ;
	}
	void pop ()
	{
		head ++ ;
	}
	void push ( Point x )
	{
		q[++tail] = x ;
	}
} Q1 ;

int ans1 , ans2 ;

class AC_auto
{
private :
	int tot , fail[maxn] , c[4][maxn] , id[maxn] , du[maxn] ;
	queue<int> Q ;
	int new_node ( int d )
	{
		int i ;
		du[tot] = d ;
		fail[tot] = 0 ;
		for ( i = 0 ; i < 4 ; i ++ ) c[i][tot] = 0 ;
		return tot ++ ;
	}
public :
	void init ()
	{
		tot = 0 ;
		while ( !Q.empty () ) Q.pop () ;
		new_node ( 0 ) ;
	}
	void insert ( char *s )
	{
		int now = 0 , d = 0 ;
		for ( ; *s ; s ++ )
		{
			d ++ ;
			int k = *s - 'a' ;
			if ( !c[k][now] ) c[k][now] = new_node ( d ) ;
			now = c[k][now] ;
		}
		id[now] = 1 ;
	}
	void get_fail ()
	{
		int i , j , u = 0 , e ;
		for ( i = 0 ; i < 4 ; i ++ ) if ( c[i][u] ) Q.push ( c[i][u] ) ;
		while ( !Q.empty  () )
		{
			u = Q.front () ;
			Q.pop () ;
			for ( i = 0 ; i < 4 ; i ++ )
			{
				if ( c[i][u] )
				{
					e = c[i][u] ;
					fail[e] = c[i][fail[u]] ;
					id[e] |= id[fail[e]] ;
					Q.push ( e ) ;
				}
				else c[i][u] = c[i][fail[u]] ;
			}
		}
	}
	void init ( int n )
	{
		int i , j , k ;
		Q1.init () ;
		ans1 = ans2 = 0 ;
		for ( i = 0 ; i <= n ; i ++ )
			for ( j = 0 ; j <= 110 ; j ++ )
				for ( k = 0 ; k <= tot ; k ++ )
					dp[i][j][k] = vis[i][j][k] = 0 ;
	}
	void bfs ( Point u , int n )
	{
		int i , j , k ;
		Point e ;
		Q1.push ( u ) ;
		vis[u.d][u.l][u.p] = dp[u.d][u.l][u.p] = 1 ;
		while ( !Q1.empty () )
		{
			u = Q1.front () ;
			Q1.pop () ;
			if ( u.d == n ) return ;
			e.d = u.d + 1 , e.l = u.l + 1 ;
			for ( i = 0 ; i < 4 ; i ++ )
			{
				e.p = c[i][u.p] ;
				if ( id[e.p] )
				{
					ans1 += dp[u.d][u.l][u.p] ;
					if ( ans1 >= mod ) ans1 -= mod ;
				}
				else
				{
					dp[e.d][e.l][e.p] += dp[u.d][u.l][u.p] ;
					if ( dp[e.d][e.l][e.p] >= mod ) dp[e.d][e.l][e.p] -= mod ;
					if ( !vis[e.d][e.l][e.p] )
					{
						Q1.push ( e ) ;
						vis[e.d][e.l][e.p] = 1 ;
					}
				}
			}
			e.l = u.l - 1 , e.p = u.p ;
			if ( e.l == 0 )
			{
				ans2 += dp[u.d][u.l][u.p] ;
				if ( ans2 >= mod ) ans2 -= mod ;
			}
			else
			{
				if ( e.l < du[e.p] ) e.p = fail[e.p] ;
				dp[e.d][e.l][e.p] += dp[u.d][u.l][u.p] ;
				if ( dp[e.d][e.l][e.p] >= mod ) dp[e.d][e.l][e.p] -= mod ;
				if ( !vis[e.d][e.l][e.p] )
				{
					Q1.push ( e ) ;
					vis[e.d][e.l][e.p] = 1 ;
				}
			}
		}
	}
	int get_p ( char *s )
	{
		int now = 0 ;
		for ( ; *s ; s ++ )
		{
			int k = *s - 'a' ;
			now = c[k][now] ;
			if ( id[now] ) return -1 ;
		}
		return now ;
	}
	void work ( int n , char *s )
	{
		int i , j , k ;
		Point u ;
		u.d = 0 ;
		u.l = strlen ( s ) ;
		u.p = get_p ( s ) ;
		if ( u.p == -1 ) ans1 ++ ;
		else init ( n ) , bfs ( u , n ) ;
	}
} ac ;

char s[1111] , s1[1111] ;
int main ()
{
	int n , m ;
	while ( scanf ( "%s" , s ) != EOF )
	{
		ac.init () ;
		scanf ( "%d%d" , &n , &m ) ;
		while ( m -- )
		{
			scanf ( "%s" , s1 ) ;
			ac.insert ( s1 ) ;
		}
		ac.get_fail () ;
		ac.work ( n , s ) ;
		printf ( "%d %d\n" , ans2 ,ans1 ) ;
	}
}
/*
aa
2
2
ab
ac
1 6
*/