自动搬运

查看原文

来自洛谷，原作者为

	Hoks end

搬运于2025-08-24 22:50:07，当前版本为作者最后更新于2024-03-18 19:26:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

比较简单的 ACAM+矩阵优化 dp。

广告：串串博客。

类似题目：

P3502 [POI2010] CHO-Hamsters。

SP1676 GEN - Text Generator。

CF696D Legen...。

P3715 [BJOI2017] 魔法咒语。

最后一题是这题的严格加强版（指加强到你被迫打个暴力）。

（这四个人认为难度单增，这题貌似可以放在最前面？）

思路分析

这个题就很小清新了，因为笔者写过这题的严格加强版。

发现是给定的 $q$ 个串不能出现即为多模匹配，考虑对于这 $q$ 个字符串建出 ACAM，给末尾打上标记，再在 fail 树建出来的时候传一下标记。

然后考虑怎么计算方案数。

由于是计数问题，且 $q$ 不大，直接考虑跑暴力 dp。

套路地设计 $dp_{i,j}$ 表示填了 $i$ 位，在 ACAM 上跑到状态 $j$ 时的方案数。

转移的时候考虑大力，尝试每个字符往下转移。

假设最后返回的状态为 $x$，那么转移方程式即为：

转移的时候记得累加一下和就行了。

最后的答案就是 $\sum\limits^{tot}_{i=1}dp_{l,n}$。

$tot$ 表示 ACAM 中的状态数，后面同。

理由也很简单，最后可能停留在 ACAM 上的任意一个点上。

接着考虑怎么优化，套路的想到把 ACAM 上的一个状态看做一个点，把走 $1$ 步的方案数的邻接矩阵 $base$ 处理出来后 $base^l$ 表示走 $l$ 步的方案数。

那这样的话最后的答案就 $\sum\limits^{tot}_{i=1}res_{0,i},res=base^l$。

构造矩阵时直接每个节点尝试往下匹配就行了，然后判断一下这两个状态是不是都可以走即可。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=210,INF=0x3f3f3f3f3f3f3f3f,mod=1e9+7;
int n,m,l,le,ans,mx,len[N],dp[N][N];char s[N][N],t[N];
struct ACAM
{
	struct node{int nxt,ed,v[26];}t[N];int tot=0;
	inline void insert(char s[],int n)
	{
		int u=0;
		for(int i=1;i<=n;i++){if(!t[u].v[s[i]-'a']) t[u].v[s[i]-'a']=++tot;u=t[u].v[s[i]-'a'];}
		t[u].ed=1;
	}
	inline void build()
	{
		queue<int>q;
		for(int i=0;i<26;i++) if(t[0].v[i]) t[t[0].v[i]].nxt=0,q.push(t[0].v[i]);
		while(!q.empty())
		{
			int u=q.front();q.pop();t[u].ed|=t[t[u].nxt].ed;
			for(int i=0;i<26;i++)
				if(t[u].v[i]) t[t[u].v[i]].nxt=t[t[u].nxt].v[i],q.push(t[u].v[i]);
				else t[u].v[i]=t[t[u].nxt].v[i];
		}
	}
}ac;
struct Matrix
{
	int a[N][N];
	Matrix(){memset(a,0,sizeof a);}
};
namespace Fast_IO
{
    static char buf[1000000],*paa=buf,*pd=buf;
    #define getchar() paa==pd&&(pd=(paa=buf)+fread(buf,1,1000000,stdin),paa==pd)?EOF:*paa++
    inline int read()
    {
        int x(0),t(1);char fc(getchar());
        while(!isdigit(fc)&&fc!=-1){if(fc=='-') t=-1;fc=getchar();}
        while(isdigit(fc)&&fc!=-1) x=(x<<1)+(x<<3)+(fc^48),fc=getchar();
        if(fc==-1) exit(0);return x*t;
    }
    inline void print(int x)
    {
        if(x<0) putchar('-'),x=-x;
        if(x>9) print(x/10);
        putchar(x%10+'0');
    }
    inline bool chk(char c) { return !(c>='a'&&c<='z'); }
    inline bool ck(char c) { return c!='\n'&&c!='\r'&&c!=-1; }
    inline void rd(char s[],int&n)
    {
        s[++n]=getchar();
        while(chk(s[n])) s[n]=getchar();
        while(ck(s[n])) s[++n]=getchar();
        n--;
    }
}
using namespace Fast_IO;
Matrix mul(Matrix x,Matrix y)
{
	Matrix res;
	for(int i=0;i<=mx;i++)
		for(int j=0;j<=mx;j++)
			for(int k=0;k<=mx;k++)
			{
				res.a[i][j]+=x.a[i][k]*y.a[k][j];
				res.a[i][j]=res.a[i][j]>=mod?res.a[i][j]%mod:res.a[i][j];
			}
	return res;
}
inline Matrix ksm(Matrix x,int y)
{
	Matrix res;for(int i=0;i<=mx;i++) res.a[i][i]=1;
	while(y)
	{
		if(y&1) res=mul(res,x);
		x=mul(x,x);y>>=1;
	}
	return res;
}
signed main()
{
	l=read(),m=read();
	for(int i=1;i<=m;i++) read(),le=0,rd(t,le),ac.insert(t,le);
	ac.build();Matrix base;mx=ac.tot;
	for(int x=0;x<=ac.tot;x++)
		for(int i=0;i<26;i++)
		{
			int v=ac.t[x].v[i];
			if(!ac.t[x].ed&&!ac.t[v].ed) base.a[x][v]++;
		}
	Matrix tt=ksm(base,l),t;t.a[0][0]=1;t=mul(t,tt);
	for(int pos=0;pos<=ac.tot;pos++) ans=(ans+t.a[0][pos])%mod;
	print(ans);
	return 0;
}