LQDFIBO - Xâu Fibonacci
Tác giả: hieult
Ngôn ngữ: C++
#include<cstdio>
#include<cmath>
#include<math.h>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
#define fi first
#define se second
#define PB push_back
#define MP make_pair
#define ep 0.00001
#define oo 111111111
#define base 100000000
#define mod 15111992
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define rep(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
//#define g 9.81
double const PI=4*atan(1.0);
using namespace std;
typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;
typedef long long int64;
void OPEN(){
freopen("A.in","r",stdin);
freopen("A.out","w",stdout);
}
int const max_size = 4;
struct Matrix{
int64 x[max_size][max_size];
Matrix(){};
Matrix(int64 a[max_size][max_size]) { for(int i = 0; i < max_size; i++) for(int j = 0; j < max_size; j++) x[i][j] = a[i][j];}
friend Matrix operator * (const Matrix &a, const Matrix &b){
Matrix c;
for(int i = 0; i < max_size; i++) for(int j = 0; j < max_size; j++){
c.x[i][j] = 0;
for(int k = 0; k < max_size; k++) c.x[i][j] = (c.x[i][j] + a.x[i][k] * b.x[k][j]) % mod;
}
return c;
}
friend Matrix operator ^ (const Matrix &a, const int &k){
if(k == 1) return a;
Matrix c = a ^ (k / 2);
if(k & 1) return c * c * a;
else return c * c;
}
void print(){
for(int i = 0; i < max_size; i++){
for(int j = 0; j < max_size; j++) printf("%lld ",x[i][j]);
printf("\n");
}
}
};
struct solon
{
int so;
long long a[35];
solon(){so = 1; a[1] = 0;}
solon(long long x){so = 1; a[1] = x;}
};
int sosanh(solon A,solon B){
if(A.so>B.so) return 1;
if(A.so<B.so) return -1;
for(int i = A.so;i>=1;i--){
if(A.a[i]>B.a[i]) return 1;
if(A.a[i]<B.a[i]) return -1;
}
return 0;
}
solon tong (solon A,solon B)
{
int du = 0;
solon C;
if(A.so<B.so)
{
C = A;
A = B;
B = C;
}
for(int i = B.so+1;i<=A.so;i++) B.a[i] = 0;
C.so = A.so;
for(int i = 1;i<=A.so;i++)
{
C.a[i] = (A.a[i]+B.a[i]+du)%base;
du = (A.a[i]+B.a[i]+du)/base;
}
if(du>0) {C.so++; C.a[C.so] = du;}
return C;
}
solon tichnho(solon A,long long k,int chuso)
{
solon C;
long long du = 0;
C.so = A.so+chuso;
for(int i = 1;i<=chuso;i++)
C.a[i] = 0;
for(int i = chuso+1;i<=chuso+A.so;i++)
{
C.a[i] = (A.a[i-chuso]*k+du)%base;
du = (A.a[i-chuso]*k+du)/base;
}
if(du>0) {C.so++; C.a[C.so] = du;}
return C;
}
solon tich(solon A,solon B)
{
solon C;
C.so = 1; C.a[1] = 0;
for(int i = 1;i<=B.so;i++)
{
C = tong(C,tichnho(A,B.a[i],i-1));
}
return C;
}
void print(solon A)
{
printf("%lld",A.a[A.so]);
for(int i = A.so-1;i>=1;i--)
printf("%08lld",A.a[i]);
}
solon hieu(solon A,solon B){
solon C; C.so = A.so;
for(int i = B.so+1;i<=A.so;i++)
B.a[i] = 0;
int du = 0;
for(int i = 1;i<=A.so;i++){
C.a[i] = A.a[i]-B.a[i]-du;
if(C.a[i]<0){
C.a[i]+=base;
du = 1;
}
}
while(C.a[C.so]==0) C.so--;
if(C.so==0) C.so = 1;
}
solon chia2(solon A){
int du = 0;
long long x;
for(int i = A.so;i>=1;i--){
x = A.a[i];
A.a[i] = (x+du*base)/2;
du = x%2;
}
if(A.a[A.so]==0) A.so--;
if(A.so==0) A.so++;
return A;
}
int KMP(string text,string pattern){
int n = text.length(), m = pattern.length(), F[m+2],i,j;
F[0] = F[1] = 0;
for(int i = 2;i<=m;i++){
j = F[i-1];
while(true){
if(pattern[j] == pattern[i-1]) { F[i] = j+1; break;}
else if(j==0) {F[i] = 0; break;}
else j = F[j];
}
}
i = j = 0;
int res = 0;
while(j<n){
if(text[j] == pattern[i]){
i++; j++;
if(i==m) res++;
}
else if(i>0) i = F[i];
else j++;
}
return res;
}
/*
void z_Function(string x, int z[]){
z[0] = 0;
int l = 0, r = -1, k;
for(int i = 1; i < n + n + 1; i++){
k = (i > r ? 0 : min(z[i - l], r - i + 1)) + 1;
while(i + k - 1 < n + n + 1 && x[k - 1] == x[i + k - 1]) k++; z[i] = --k;
if(i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
}
}
*/
int main(){
// OPEN();
int n;
string s1, s2, s, s3;
cin >> n >> s1 >> s2 >> s;
while((s1.length() < s.length() || s2.length() < s.length()) && n > 1){
s3 = s2;
s2 = s2 + s1;
s1 = s3;
n--;
}
s3 = s2 + s1;
if(n == 1) printf("%d", KMP(s1, s));
else if(n == 2) printf("%d", KMP(s2, s));
else if(n == 3) printf("%d", KMP(s3, s));
else if(n == 4) printf("%d", KMP(s3 + s2, s));
else{
int n1 = s1.length(), n2 = s2.length(), ns = s.length();
int64 t1 = KMP((s1.substr(n1 - ns + 1, ns - 1) + s2.substr(0, ns - 1)), s);
int64 t2 = KMP((s2.substr(n2 - ns + 1, ns - 1) + s2.substr(0, ns - 1)), s);
int64 t = t1 + t2;
int64 f4 = KMP(s3 + s2, s), f3 = KMP(s3, s), f2 = KMP(s2, s);
solon T;
solon T1 = solon(t1);
solon T2 = solon(t2);
solon F4 = solon(f4);
solon F3 = solon(f3);
solon F2 = solon(f2);
solon Fthe;
for(int i = 5; i <= n; i++){
if(i & 1){
T = T2;
}
else T = T1;
Fthe = tong(F4, tong(F3, T));
F3 = F4;
F4 = Fthe;
}
print(F4);
}
}