牛客练习赛63 牛牛的斐波那契字符串矩阵乘法 KMP

LINK：牛牛的斐波那契字符串

虽然sb的事实没有改变但是也不会改变。

赛时看了E和F题都不咋会写所以弃疗了。

中午又看了一遍F 发现很水差分了一下就过了。

这是下午和古队长讨论+看题解的神仙做法的时候突然想到的。

问题的难点在于 a和b的长度有可能是小于s的所以递推不了只能暴力。

暴力的背后藏着正解。可以发现当a和b的长度扩大到大于s时容易发现每次s匹配的不可能横跨a b了所以此时只有可能是a的后缀接b的后缀或者b的后缀接a的后缀。

而这个我们可以递推式子分奇偶考虑。然后就可以直接递推了。

题解的神仙做法是杜教BM 不过做法过于神仙也没有学习的必要所以弃疗。

直接考虑矩阵乘法这个东西虽然带系数不过矩阵是可以列出的还很容易我列了一个\(4\cdot 4\)的。

细节比较繁琐。值得注意。

const ll MAXN=1000010;

ll n,ans,cnt=2,ww=2,d1,d2;

ll nex[MAXN],f[4],g[4];

string a[2],s,cc;

inline void KMP(string b)

{

	ll j=-1;ans=0;

	for(ui ll i=0;i<b.size();++i)

	{

		while(j!=-1&&s[j+1]!=b[i])j=nex[j];

		if(b[i]==s[j+1])++j;

		if(j==(ll)s.size()-1){j=nex[j];++ans;}

	}

}

struct wy

{

	ll a[4][4];

	wy(){memset(a,0,sizeof(a));}

	inline wy friend operator *(wy a,wy b)

	{

		wy c;

		rep(0,3,i)rep(0,3,j)rep(0,3,k)

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

		return c;

	}

	inline wy friend operator ^(wy a,ll p)

	{

		while(p)

		{

			if(p&1)

			{

				rep(0,3,i)g[i]=f[i],f[i]=0;

				rep(0,3,i)rep(0,3,j)f[i]=(f[i]+a.a[j][i]*g[j])%mod;

			}

			p=p>>1;a=a*a;

		}

		return a;

	}

}T;

signed main()

{

	//freopen("1.in","r",stdin);

	ios::sync_with_stdio(false);

	cin>>n;cin>>a[0];cin>>a[1];cin>>s;

	memset(nex,-1,sizeof(nex));

	ll j=-1;

	for(ui ll i=1;i<s.size();++i)

	{

		while(j!=-1&&s[j+1]!=s[i])j=nex[j];

		if(s[j+1]==s[i])++j;

		nex[i]=j;

	}

	if(n==1){KMP(a[0]);putl(ans);return 0;}

	if(n==2){KMP(a[1]);putl(ans);return 0;}

	ll w1=0,w2=1;//putl(ww);

	while(a[0].size()<s.size()||a[1].size()<s.size())

	{

		a[w1]=a[w1]+a[w2];

		swap(w1,w2);++ww;

		if(ww==n){KMP(a[w2]);putl(ans);return 0;}

	}

	//求出递推常数 d1和d2.偶数为 w2+w1 奇数为w2+w2;

	//cout<<a[w1]<<' '<<a[w2]<<endl;putl(ww);

	ll kk=a[w2].size()-s.size()+1;

	for(ui i=kk;i<a[w2].size();++i)cc+=a[w2][i];

	for(ui i=0;i<s.size()-1;++i)cc+=a[w2][i];

	//cout<<cc<<endl;

	KMP(cc);d1=ans;cc="";//putl(ans);

	for(ui i=kk;i<a[w2].size();++i)cc+=a[w2][i];

	for(ui i=0;i<s.size()-1;++i)cc+=a[w1][i];

	//cout<<cc<<endl;

	KMP(cc);d2=ans;cc="";//putl(ans);

	a[w1]=a[w1]+a[w2];++ww;

	swap(w1,w2);

	KMP(a[w1]);f[0]=ans;

	KMP(a[w2]);f[1]=ans;

	if(ww==n){putl(f[1]);return 0;}

	n-=ww;f[2]=d2;f[3]=d1;

	T.a[0][1]=T.a[1][0]=T.a[1][1]=T.a[2][1]=T.a[2][3]=T.a[3][2]=1;

	T=T^n;putl(f[1]);return 0;

}

巴特西

牛客练习赛63 牛牛的斐波那契字符串矩阵乘法 KMP

最新文章

热门文章

巴特西

牛客练习赛63 牛牛的斐波那契字符串 矩阵乘法 KMP

最新文章

热门文章

牛客练习赛63 牛牛的斐波那契字符串矩阵乘法 KMP