fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define matrix vector<vector<ll>>
  4. #define base  15111992
  5. using namespace std;
  6. string s1, s2, t, s;
  7. int t0,t1,t2,t3,n;
  8. matrix  s1s2={{0,1,0,0},{1,1,0,0},{0,1,1,0},{0,0,0,1}};
  9. matrix  s2s2={{0,1,0,0},{1,1,0,0},{0,0,1,0},{0,1,0,1}};
  10. matrix d,a;
  11. matrix c;
  12.  
  13. matrix operator * (const matrix &a, const matrix &b) {
  14.     matrix c ={{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0}};
  15.     for (int i = 0; i < 4; i++) {
  16.         for (int j = 0; j < 4; j++) {
  17.             for (int k = 0; k < 4; k++) {
  18.                 c[i][j] = (c[i][j] + (a[i][k] * b[k][j])  % base )% base ;
  19.             }
  20.         }
  21.     }
  22.     return c;
  23. }
  24. int sub_(string a, string b) {
  25.     string st;
  26.     int dem=0;
  27.     for (int i=0 ; i<b.length()-a.length()+1 ; i++)
  28.     {
  29.         st="";
  30.         for (int j=i ; j<(i+a.length()); j++)
  31.         {
  32.             st=st+b[j];
  33.         }
  34.         if (st==a) dem++;
  35.     }
  36.     return dem;
  37.    }
  38. matrix tinh(matrix a ,ll n) {
  39.     if (n == 1) return a;
  40.     matrix t = tinh(a,n / 2);
  41.     t=t*t;
  42.     if (n % 2 == 1) t=t *a;
  43.     return t;
  44. }
  45. void prepare()
  46. {
  47.     c=s1s2*s2s2;
  48.     d={{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0}};
  49.     a={{sub_(s,s2),sub_(s,s2+s1),sub_(s,s1+s2)-sub_(s, s1)-sub_(s,s2),sub_(s,s2+s2)-2*sub_(s,s2)},
  50.     {0,0,0,0},{0,0,0,0},{0,0,0,0}};
  51.     n--;
  52. }
  53. void mul()
  54. {
  55.     prepare();
  56.     if (n==0)
  57.     {
  58.          cout<<sub_(s,s2+s1)%base<<endl;
  59.          return ;
  60.     }
  61.     if (n==1)
  62.     {
  63.         a=a*s1s2;
  64.         cout<<a[0][1]%base<<endl;
  65.         return;
  66.     }
  67.     if (n%2==0)
  68.     {
  69.         d=tinh(c,n/2);
  70.     }
  71.     else
  72.     if (n%2==1)
  73.     {
  74.         n--;
  75.         d=tinh(c,n/2)*s1s2;
  76.     }
  77.  
  78.     d=a*d;
  79.     cout<<d[0][1]%base;
  80. }
  81. int main() {
  82. 	cin>>n;
  83. 	cin>>s1;
  84. 	cin>>s2;
  85. 	cin>>s;
  86.     n=n-2;
  87.  
  88. 	string s3;
  89. 	for (int i=1;i<=30 &&n>0 ;i++)
  90.     {
  91.         s3=s2+s1;
  92.         s1=s2;
  93.         s2=s3;
  94.         n--;
  95.         if (s1.length() >= s.length() || s2.length() >= s.length()) break;
  96.     }
  97.     if(n==0)cout << sub_(s, s2)<<endl ;
  98.     else mul();
  99.     return 0;
  100. }
  101.  
  102.  
  103.  
  104.  
Success #stdin #stdout 0s 4448KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/H3dMwo
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!