列表

详情


NC204122. 牛牛的斐波那契字符串

描述

定义字符串的斐波那契序列,当i>=3时字符串的加法定义为字符串直接拼接。

给定A,B两个初始串,以及一个字符串S,牛牛想知道fibstr_n,中包含了多少个S串。请统计数目告诉牛牛。由于这个数字很大,请输出答案mod 后的结果。

输入描述

第一行输入一个正整数n表示第n个fibstr。

接下来三行分别输入三个字符串,A,B,S,表示两个初始串以及查询串。

所有输入的字符串仅由小写英文字母组成。

输出描述

输出答案mod  后的结果

示例1

输入:

10
a b bab

输出:

21

说明:

fibstr_{10}="bababbababbabbababbababbabbababbabbababbababbabbababbab"

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 17ms, 内存消耗: 3204K, 提交时间: 2020-05-08 23:07:32

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7,MAXN=3;
int i,i0,n,nex[100005];
string pre[55],suf[55],s,str[55];
struct MAT
{
    int mat[MAXN][MAXN];
    MAT operator*(const MAT &a)const
    {
        MAT b;
        memset(b.mat,0,sizeof(b.mat));
        for(int i=0;i<MAXN;i++)
        {
            for(int j=0;j<MAXN;j++)
            {
                for(int k=0;k<MAXN;k++)b.mat[i][j]=(b.mat[i][j]+(long long)mat[i][k]*a.mat[k][j])%mod;
            }
        }
        return b;
    }
};
MAT Mqpow(MAT base,long long b)
{
    MAT r;
    for(int i=0;i<MAXN;i++)for(int j=0;j<MAXN;j++)r.mat[i][j]=i==j;
    while(b)
    {
        if(b&1)r=base*r;
        base=base*base;
        b>>=1;
    }
    return r;
}
void cal_nex(string str,int len)
{
    nex[0]=-1;
    for (int q=1,k=-1;q<len;q++)
    {
        while(k!=-1&&str[k+1]!=str[q])k=nex[k];
        if (str[k+1]==str[q])k++;
        nex[q]=k;
    }
}
int KMP(string str,int slen,string ptr,int plen)
{
    cal_nex(ptr,plen);
	int cnt=0;
    for(int i=0,k=-1;i<slen;i++)
    {
        while(k>-1&&ptr[k+1]!=str[i])k=nex[k];
        if(ptr[k+1]==str[i])k++;
        if(k==plen-1)cnt++,k=nex[k];
    }
    return cnt;
}
int main()
{
    long long n;
	cin>>n;
	cin>>str[1]>>str[2]>>s;
    int d=0;
	for(int i=3;!d&&i<=n;i++)
	{
		if(i!=3&&str[i-1].length()>=s.length()&&str[i-2].length()>=s.length())d=i;
		else str[i]=str[i-2]+str[i-1];
	}
    if(!d)cout<<KMP(str[n],str[n].length(),s,s.length())<<endl;
    else
    {
        str[1]=str[d-2],str[2]=str[d-1];
        pre[1]=str[1].substr(0,s.length()-1);
		suf[1]=str[1].substr(str[1].length()-s.length()+1,s.length()-1);
        pre[2]=str[2].substr(0,s.length()-1);
		suf[2]=str[2].substr(str[2].length()-s.length()+1,s.length()-1);
        str[3]=suf[2]+pre[2];
        str[4]=suf[2]+pre[1];
        n-=d-2;
        int x=KMP(str[4],str[4].length(),s,s.length()),y=KMP(str[3],str[3].length(),s,s.length());
        MAT start,r;
        start.mat[0][0]=2,start.mat[0][1]=1,start.mat[0][2]=x+y;
        start.mat[1][0]=1,start.mat[1][1]=1,start.mat[1][2]=y;
        start.mat[2][0]=0,start.mat[2][1]=0,start.mat[2][2]=1;
        r.mat[0][0]=KMP(str[2],str[2].length(),s,s.length()),r.mat[0][1]=0,r.mat[0][2]=0;
        r.mat[1][0]=KMP(str[1],str[1].length(),s,s.length()),r.mat[1][1]=0,r.mat[1][2]=0;
        r.mat[2][0]=1,r.mat[2][1]=0,r.mat[2][2]=0;
        cout<<(Mqpow(start,n/2)*r).mat[!(n%2)][0]<<endl;
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 39ms, 内存消耗: 37476K, 提交时间: 2020-05-08 21:43:47

#include<bits/stdc++.h>
#define mems(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MS=5,mod=1e9+7,N=2e6+5;
string s1="A",s2="B";
ull base=233,invb=7204522363551799129,f[N],invf[N],hs[N];
ull geths(int l,int r)
{
    return (hs[r]-hs[l-1])*invf[l-1];
}
struct Mat
{
    ll a[MS][MS];
    int n,m;
    Mat(int n=0,int m=0):n(n),m(m) { mems(a,0);}
    Mat operator*(const Mat&B)const
    {
        Mat C(n,B.m);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=B.m;j++)
                for(int k=1;k<=m;k++)
                C.a[i][j]=(C.a[i][j]+a[i][k]*B.a[k][j]%mod)%mod;
        return C;
    }
};
int m;
ll n,f1,f2,f3,bb,ba;
string a,b,t,s;
ull sum;
int get(string s)
{
    for(int i=1;i<=s.size();i++)
        hs[i]=hs[i-1]+f[i]*(s[i-1]-'a');
    int ans=0;
    for(int i=1;i+m-1<=s.size();i++)
        if(geths(i,i+m-1)==sum) ans++;
    return ans;
}
int solve(string a,string b)
{
    string s=a+b;
    for(int i=1;i<=s.size();i++)
        hs[i]=hs[i-1]+f[i]*(s[i-1]-'a');
    int ans=0;
    for(int i=1;i<=a.size()&&i+m-1<=s.size();i++)
        if(i+m-1>a.size()&&geths(i,i+m-1)==sum) ans++;
    return ans;
}
Mat qpow(Mat a,ll n)
{
    Mat ans(4,4);
    for(int i=1;i<=4;i++) ans.a[i][i]=1;
    while(n)
    {
        if(n&1) ans=ans*a;
        a=a*a;
        n>>=1;
    }
    return ans;
}
int main()
{
    f[0]=invf[0]=1;
    for(int i=1;i<N;i++) f[i]=f[i-1]*base,invf[i]=invf[i-1]*invb;
    cin>>n>>a>>b>>s;
    m=s.size();
    ll now=2;
    for(int i=1;i<=s.size();i++)
        sum=sum+f[i]*(s[i-1]-'a');
    if(n==1) {cout<<get(a)<<endl;return 0;}
    else if(n==2) {cout<<get(b)<<endl;return 0;}
    while(a.size()<=s.size()||b.size()<=s.size())
    {
        now++;
        string k=a+b;
        a=b;b=k;
        if(now==n)
        {
            cout<<get(b)<<endl;return 0;
        }
    }
    f1=get(b);f2=get(a+b);
    now++;
    if(now==n)
    {
        cout<<f2<<endl;return 0;
    }
    ba=solve(b,a);
    bb=solve(b,b);
    Mat A(4,4);
    A.a[1][1]=A.a[1][2]=A.a[1][3]=1;
    A.a[2][1]=1;
    A.a[3][4]=1;
    A.a[4][3]=1;
    A=qpow(A,n-now);
    ll res=A.a[1][1]*f2%mod+A.a[1][2]*f1%mod+A.a[1][3]*ba%mod+A.a[1][4]*bb%mod;
    printf("%lld\n",(res%mod+mod)%mod);
}

上一题