fork download 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cstring>
  4. #include <complex>
  5. #include <cassert>
  6. #include <cstdlib>
  7. #include <cstdio>
  8. #include <bitset>
  9. #include <vector>
  10. #include <string>
  11. #include <cmath>
  12. #include <ctime>
  13. #include <queue>
  14. #include <list>
  15. #include <map>
  16. #include <set>
  17.  
  18. #define all(x) (x).begin(), (x).end()
  19. #define type(x) __typeof((x).begin())
  20. #define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)
  21.  
  22. #ifdef KAZAR
  23.     #define eprintf(...) fprintf(stderr,__VA_ARGS__)
  24. #else
  25.     #define eprintf(...) 0
  26. #endif
  27.  
  28. using namespace std;
  29.  
  30. template<class T> inline void umax(T &a,T b){if(a<b) a = b ; }
  31. template<class T> inline void umin(T &a,T b){if(a>b) a = b ; }
  32. template<class T> inline T abs(T a){return a>0 ? a : -a;}
  33. template<class T> inline T gcd(T a,T b){return __gcd(a, b);}
  34. template<class T> inline T lcm(T a,T b){return a/gcd(a,b)*b;}
  35.  
  36. const int inf = 1e9 + 143;
  37. const long long longinf = 1e18 + 143;
  38.  
  39. inline int read(){int x;scanf(" %d",&x);return x;}
  40.  
  41. const int N = 55;
  42.  
  43. int n, m;
  44. unsigned a[N][N], res[N][N], t[N][N];
  45.  
  46. void mul(unsigned a[N][N],unsigned b[N][N]){
  47.     for(int i = 0; i < n; i++){
  48.         for(int j = 0; j < n; j++){
  49.             t[i][j] = 0;
  50.             for(int k = 0; k < n; k++)
  51.                 t[i][j] += a[i][k] * b[k][j];
  52.         }
  53.     }
  54.     for(int i = 0; i < n; i++)
  55.         for(int j = 0; j < n; j++)
  56.             a[i][j] = t[i][j];
  57. }
  58.  
  59. void solve(){
  60.     string alp, s;
  61.     int d = read();
  62.     cin >> alp >> s;
  63.     m = alp.size();
  64.     n = s.size();
  65.     memset(a, 0, sizeof a);
  66.     for(int len = 0; len < n; len++){
  67.         for(int add = 0; add < m; add++){
  68.             string temp = s.substr(0, len);
  69.             temp += alp[add];
  70.             for(int nlen = len + 1; nlen >= 0; nlen--){
  71.                 if(nlen == 0 || temp.substr(len + 1 - nlen, nlen) == s.substr(0, nlen)){
  72.                     if(nlen != n)
  73.                         a[len][nlen]++;
  74.                     break;
  75.                 }
  76.             }
  77.         }
  78.     }
  79.     for(int i = 0; i < n; i++){
  80.         for(int j = 0; j < n; j++){
  81.             res[i][j] = (i == j)? 1 : 0;
  82.         }
  83.     }
  84.     while(d > 0){
  85.         if(d & 1)
  86.             mul(res, a);
  87.         mul(a, a);
  88.         d >>= 1;
  89.     }
  90.     unsigned ans = 0;
  91.     for(int i = 0; i < n; i++)
  92.         ans += res[0][i];
  93.     cout << ans << endl;
  94. }
  95.  
  96. int main(){
  97.  
  98. #ifdef KAZAR
  99.     freopen("f.input","r",stdin);
  100.     freopen("f.output","w",stdout);
  101.     freopen("error","w",stderr);
  102. #endif
  103.  
  104.     int tc = read();
  105.  
  106.     for(int t = 0; t < tc; t++){
  107.         printf("Case %d: ", t + 1);
  108.         solve();
  109.     }
  110.  
  111.     return 0;
  112. }
Success #stdin #stdout 0s 3336KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/wD1ktK
language:
C++ (gcc 8.3)
created:
10 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!