fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef unsigned long long LL;
  5. typedef pair<LL,LL> pii;
  6. typedef vector<LL> vi;
  7.  
  8. const LL Mod = (4294967296ULL);
  9. const LL NN = 60;
  10.  
  11. char msg[NN],pat[NN];
  12.  
  13. LL LPS[NN],aut[NN][NN];
  14. LL ans[NN][NN],def[NN][NN],temp[NN][NN];
  15. int N;
  16.  
  17. void build_kmp(LL n,LL m){
  18.     assert(n < NN and m < NN);
  19.     LL k = LPS[0] = 0;
  20.     for(LL i = 1; i < n; ++i){
  21.         while(k > 0 and pat[i] != pat[k])
  22.             k = pat[k-1];
  23.         LPS[i] = (k += (pat[i] == pat[k]));
  24.     }
  25.  
  26.     for(LL k = 0; k < n; ++k) for(LL i = 0; i < m; ++i){
  27.         if (k > 0 and pat[k] != msg[i])
  28.             aut[k][i] = aut[LPS[k-1]][i];
  29.         else
  30.             aut[k][i] = k + (pat[k] == msg[i]);
  31.     }
  32. }
  33.  
  34. void mul(LL A[NN][NN],LL B[NN][NN],LL Ans[NN][NN]){
  35.     for(int i = 0; i < N; ++i) for(int j = 0; j < N; ++j){
  36.         Ans[i][j] = 0ULL;
  37.         for(int k = 0; k < N; ++k)
  38.             Ans[i][j] = ((A[i][k]*B[k][j])%Mod + Ans[i][j])%Mod;
  39.     }
  40. }
  41.  
  42. void identity(LL A[NN][NN]){
  43.     memset(A,0,sizeof(A));
  44.     for(int i = 0; i < N; ++i)
  45.         A[i][i] = 1ULL;
  46. }
  47.  
  48. void f(LL n){
  49.     if (n == 0){
  50.         identity(ans);
  51.         return;
  52.     }
  53.  
  54.     f(n/2);
  55.     mul(ans,ans,temp);
  56.     memcpy(ans,temp,sizeof(temp));
  57.     if (n & 1) {
  58.         mul(ans,def,temp);
  59.         memcpy(ans,temp,sizeof(temp));
  60.     }
  61. }
  62.  
  63. LL solve(){
  64.     memset(ans,0,sizeof(ans));
  65.     memset(def,0,sizeof(def));
  66.     memset(aut,0,sizeof(aut));
  67.  
  68.     LL a,b;
  69.     LL n; cin >> n;
  70.     scanf("%s%s",msg,pat);
  71.  
  72.     //dbg(msg); dbg(pat);
  73.     b = (LL)strlen(msg);
  74.     N = a = (LL)strlen(pat);
  75.     build_kmp(a,b);
  76.  
  77.     for(LL i = 0; i < a; ++i) for(LL j = 0; j < b; ++j){
  78.         LL nxt = aut[i][j];
  79.         def[i][nxt] += (nxt < a);
  80.     }
  81.  
  82.     f(n);
  83.     LL cnt = 0ULL;
  84.     for(LL k = 0; k < a; ++k)
  85.         cnt = (cnt + ans[0][k])%Mod;
  86.     return cnt;
  87. }
  88.  
  89. int main()
  90. {
  91.     LL t; cin >> t;
  92.     for(LL i = 1; i <= t; ++i){
  93.         cout << "Case " << i << ": " << solve() << endl;
  94.     }
  95.     return 0;
  96. }
  97.  
Success #stdin #stdout 0s 3460KB
comments (?)
stdin
copy 
3

3

ab

ab

4

acd

ca

5

ab

aaa
stdout
copy 
Case 1: 4
Case 2: 55
Case 3: 24
https://ideone.com/3PTR9S
language:
C++14 (gcc 8.3)
created:
10 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!