fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define rep(i,a,b) for(ll i=a;i<b;++i)
  4. #define per(i,a,b) for(ll i=a-1;i>=b;--i)
  5. #define vi vector<ll>
  6. #define vvi vector<vector<ll> >
  7. #define piii pair<ll,pair<ll,ll> >
  8. #define pii pair<ll,ll>
  9. #define pb push_back
  10. #define mp make_pair
  11. #define lb lower_bound
  12. #define ub upper_bound
  13. #define F first
  14. #define S second
  15. #define SPD ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
  16. using namespace std;
  17.  
  18. string a, b, s;
  19. ll f0, f1, M = 15111992;
  20. vvi mta(3, vi(3, 0)), mtb(3, vi(3, 0));
  21.  
  22. ll find_string(string s1, string s2) {
  23.     ll r = 0;
  24.     rep(i, 0, s1.length() - s2.length() + 1)r += (s1.substr(i, s2.length()) == s);
  25.     return r;
  26. }
  27. void matrix_cal() {
  28.     f0 = find_string(a, s);
  29.     f1 = find_string(b, s);
  30.     ll tmp = find_string(a + b, s) - f0 - f1;
  31.     mta = {{0, 1, 0},
  32.         {1, 1, 0},
  33.         {0, tmp, 1}
  34.     };
  35.     tmp = find_string(b + a, s) - f0 - f1;
  36.     mtb = {{0, 1, 0},
  37.         {1, 1, 0},
  38.         {0, tmp, 1}
  39.     };
  40. }
  41. vvi matrix_mul(vvi m1,vvi m2){
  42.     vvi rs(3,vi(3,0));
  43.     rep(i,0,m1.size())rep(j,0,m1.size()){
  44.         rep(l, 0, m1.size())rs[i][j] = (rs[i][j] + m1[i][l] * m2[l][j]) % M;
  45.     }
  46.     return rs;
  47. }
  48. ll fibo_cal(ll i){
  49.     //cout << n << '\n';
  50.     //cout << f0 << ' ' << f1 << '\n';
  51.     vvi mtrs = {{1, 0, 0},
  52.                 {0, 1, 0},
  53.                 {0, 0, 1}};
  54.     mtb = matrix_mul(mta, mtb);
  55.     ll t = i / 2;
  56.     while(t){
  57.         if(t & 1)mtrs = matrix_mul(mtrs, mtb);
  58.         mtb = matrix_mul(mtb, mtb);
  59.         t >>= 1;
  60.     }
  61.     if(i % 2)mtrs = matrix_mul(mtrs, mta);
  62.     return (1LL * f0 * mtrs[0][1] + f1 * mtrs[1][1] + 1 * mtrs[2][1]) % M;
  63. }
  64. void solve(ll i){
  65.     --i;
  66.     while (--i > 0 && a.length() < s.length()) {
  67.         a = a + b;
  68.         swap(a, b);
  69.     }
  70.     if (!i) {
  71.         cout << find_string(b, s) << '\n';
  72.         return;
  73.     }
  74.     matrix_cal();
  75.     cout << fibo_cal(i) << '\n';
  76. }
  77. int main() {
  78.     SPD;
  79.     ll i; cin >> i >> a >> b >> s;
  80.     solve(i);
  81.     //rep(i, 3, 21)solve(i);
  82.     return 0;
  83. }
  84.  
Time limit exceeded #stdin #stdout 5s 4492KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Nr4FQl
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
public

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!