游客 注册 | 登录
中文 | En

3843 - 字符串

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 256 MB

为了庆祝祖国生日，小Z学起了斐波那契数列。

F[0]=0

F[1]=1

F[i]=F[i-2]+F[i-1]

小Z突发奇想，要是这个F是一个string类型该多有趣。

S[0]=”0”

S[1]=”1”

S[i]=S[i-2]S[i-1] (表示连接两个字符串)。

小Z经过科学的计算后发现S[N]会很长很长，但是他只想知道一个问题的答案，就是小Z心中的0/1串T在S[N]中出现了多少次。

这次模P。

题目输入

输入文件string.in。

第一行三个整数N,M,P，N如题中所述、M为串T的长度、P为需要取模的数。

第二行为一个长度为M的0/1串。

题目输出

输出文件string.out。

仅包含一个整数，为出现次数模P之后的值。

输入/输出样例

输入格式

7 3 100
101

输出格式

8

C++解答

#define MAXS 5UL
#define MAXM 10010UL

#define ll long long

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>

using namespace std;

int p;

struct Martix{
	ll s[MAXS][MAXS];
	inline void clr(){memset(s,0,sizeof(s));return;}
	inline void Install(){clr();s[1][2]=1;s[2][1]=2;s[2][3]=1;s[3][1]=1;s[4][1]=1;s[4][4]=1;return;}
	inline void Unit(){clr();for(int i=1;i<=4;i++) s[i][i]=1;return;}
	inline void Build(int a,int b,int c,int d){clr();s[1][1]=a;s[1][2]=b;s[1][3]=c;s[1][4]=d;return;}
	friend Martix operator * (Martix a,Martix b){
		Martix temp;temp.clr();
		for(int i=1;i<=4;i++){
			for(int j=1;j<=4;j++){
				for(int k=1;k<=4;k++){
					temp.s[i][j]=(temp.s[i][j]+a.s[i][k]*b.s[k][j])%p;
				}
			}
		}
		return temp;
	}
};

int n,m,next2[MAXM],t1,t2,a1,a2,T,tp;

string ls1="0",ls2="1",metr,r;

inline void GetNext(){
	for(int i=1,k=0;i<m;i++){
		while(metr[i]!=metr[k]&&k) k=next2[k];
		if(metr[i]==metr[k]) k++;
		next2[i+1]=k;
	}
	return;
}

inline int KMP(string link){
	int len2=link.size(),Ans=0;
	for(int i=0,j=0;i<len2;i++){
		while(metr[j]!=link[i]&&j) j=next2[j];
		if(metr[j]==link[i]) j++;
		if(j==m){
			Ans++;j=next2[j];
		}
	}
	return Ans;
}

Martix R,Ans,cy;

inline void Work(){
	string link;
	for(int i=2;i<=n;i++) r=ls2,ls2=ls1+ls2,ls1=r;
	if(n==0) link="0";
	else link=ls2;
	GetNext();printf("%d",KMP(link)%p);
	return;
}

int main(){
	scanf("%d%d%d",&n,&m,&p);cin>>metr;
	if(n<20){
		Work();return 0;
	}
	while(ls1.size()<m||ls2.size()<m) r=ls2,ls2=ls1+ls2,ls1=r,tp++;
	GetNext();a1=KMP(ls1),a2=KMP(ls2),t1=KMP(ls1+ls2)-a1-a2,t2=KMP(ls2+ls1)-a1-a2,T=t1+t2;
	//tp == ls1 tp+1 == ls2 
	//f[tp] = a1,f[tp+1] = a2,f[tp+2]=t1+a1+a2;
	R.Build(t1+a1+a2,a2,a1,T);// tp+2 --> n
	int k=n-(tp+2);Ans.Unit();cy.Install(); // Ans=cy^k  Ans=R*Ans;
	while(k){
		if(k&1) Ans=Ans*cy;
		k>>=1;cy=cy*cy;
	}R=R*Ans;
	printf("%lld\n",R.s[1][1]);
	return 0;
}
请先登陆