【题解】Luogu P5337 [TJOI2019]甲苯先生的字符串

原题传送门

我们设计一个\(26*26\)的矩阵\(A\)表示\(a~z\)和\(a~z\)是否能够相邻，这个矩阵珂以由\(s1\)得出。答案显然是矩阵\(A^{len_{s2}-1}\)的所有元素之和，矩阵快速幂即可

#include <bits/stdc++.h>

#define ll long long

#define mod 1000000007

using namespace std;

inline void write(register int x)

{

    if(!x)putchar('0');if(x<0)x=-x,putchar('-');

    static int sta[20];register int tot=0;

    while(x)sta[tot++]=x%10,x/=10;

    while(tot)putchar(sta[--tot]+48);

}

struct mat{

	int a[26][26];

	inline mat()

	{

		memset(a,0,sizeof(a));

	}

	inline mat operator*(const mat&b)const{

		mat c;

		for(register int i=0;i<26;++i)

			for(register int j=0;j<26;++j)

				for(register int k=0;k<26;++k)

					c.a[i][j]=(c.a[i][j]+1ll*a[i][k]*b.a[k][j])%mod;

		return c;

	}

}s;

inline mat fastpow(register mat a,register ll b)

{

	mat ret;

	for(register int i=0;i<26;++i)

		ret.a[i][i]=1;

	while(b)

	{

		if(b&1)

			ret=ret*a;

		a=a*a;

		b>>=1;

	}

	return ret;

}

ll n,ans;

char str[100005];

int main()

{

	scanf("%lld%s",&n,str+1);

	int len=strlen(str+1);

	for(register int i=0;i<26;++i)

		for(register int j=0;j<26;++j)

			s.a[i][j]=1;

	for(register int i=1;i<len;++i)

		s.a[str[i]-'a'][str[i+1]-'a']=0;

	mat res=fastpow(s,n-1);

	for(register int i=0;i<26;++i)

		for(register int j=0;j<26;++j)

			ans=(ans+res.a[i][j])%mod;

	write(ans);

	return 0;

}

巴特西

【题解】Luogu P5337 [TJOI2019]甲苯先生的字符串

原题传送门

我们设计一个\(26*26\)的矩阵\(A\)表示\(a~z\)和\(a~z\)是否能够相邻，这个矩阵珂以由\(s1\)得出。答案显然是矩阵\(A^{len_{s2}-1}\)的所有元素之和，矩阵快速幂即可

最新文章

热门文章