题意

给出字符串的长度 \(n\) ，以及该字符串是由哪些小写字母组成，现给出一个坏串 \(S\) ，求存在多少种不同的字符串，使得其子串不含坏串。

\(1 \leq n \leq 10^9\)

\(1 \leq |S| \leq 50\)

思路

矩阵快速幂优化 \(\text{dp}\) 是真的常见，在同层状态数不多，但层数很多的时候，要考虑矩阵快速幂优化 \(\text{dp}\) 。

每一层的状态 \(dp[i]\) 表示匹配到哪里，再枚举给定的字母进行转移，只要不匹配到 \(S\) 结尾都是一个合法的转移，转移系数为 \(1\) 。剩下就是板子了。

代码

#include<bits/stdc++.h>

#define FOR(i,x,y) for(int i=(x),i##END=(y);i<=i##END;++i)

#define DOR(i,x,y) for(int i=(x),i##END=(y);i>=i##END;--i)

typedef long long LL;

typedef unsigned int uint;

using namespace std;

const int N=53;

struct Matrix

{

	int n,m;uint a[N][N];

	uint *operator [](const int x){return a[x];}

	void resize(int _n,int _m){n=_n,m=_m;}

	Matrix operator *(const Matrix &_)const

	{

		Matrix res;res.resize(n,_.m);

		FOR(i,1,n)FOR(j,1,_.m)

		{

			res[i][j]=0;

			FOR(k,1,m)res[i][j]+=a[i][k]*_.a[k][j];

		}

		return res;

	}

	Matrix operator *=(const Matrix &_){return (*this)=(*this)*_;}

}A,B;

char d_c[30],str[N];

int c_d[256];

int f[N],F[N][30];

int n,m,l;

Matrix Pow(Matrix a,int p)

{

	Matrix res;res.resize(a.n,a.n);

	FOR(i,1,res.n)FOR(j,1,res.n)res[i][j]=(i==j);

	for(;p>0;p>>=1,a*=a)if(p&1)res*=a;

	return res;

}

int main()

{

	int Case;

	scanf("%d",&Case);

	FOR(cas,1,Case)

	{

		scanf("%d",&n);

		scanf("%s",d_c+1);

		scanf("%s",str+1);

		l=strlen(d_c+1);

		m=strlen(str+1);

		FOR(i,1,l)c_d[(int)d_c[i]]=i;

		f[1]=f[2]=1;FOR(i,1,l)F[1][i]=1+(i==c_d[(int)str[1]]);

		FOR(i,2,m)

		{

			f[i+1]=F[f[i]][c_d[(int)str[i]]];

			FOR(j,1,l)

			{

				if(c_d[(int)str[i]]==j)F[i][j]=i+1;

				else F[i][j]=F[f[i]][j];

			}

		}

		A.resize(1,m),B.resize(m,m);

		FOR(i,1,m)A[1][i]=0;

		FOR(i,1,m)FOR(j,1,m)B[i][j]=0;

		A[1][1]=1;

		FOR(i,1,m)FOR(j,1,l)if(F[i][j]<=m)B[i][F[i][j]]++;

		A*=Pow(B,n);

		uint ans=0;

		FOR(i,1,m)ans+=A[1][i];

		printf("Case %d: %u\n",cas,ans);

	}

	return 0;

}