NC204122. 牛牛的斐波那契字符串
描述
输入描述
第一行输入一个正整数n表示第n个fibstr。
接下来三行分别输入三个字符串,A,B,S,表示两个初始串以及查询串。
所有输入的字符串仅由小写英文字母组成。
输出描述
输出答案mod后的结果
示例1
输入:
10 a b bab
输出:
21
说明:
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); }