fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define F first
  5. #define S second
  6. #define pb push_back
  7. #define all(a) a.begin(), a.end()
  8.  
  9. typedef long long ll;
  10. typedef pair<int, int> ii;
  11.  
  12. const int N = 25 + 1;
  13.  
  14. int f[N][N][N];
  15. char a[N][N];
  16. int lps[N * 2];
  17. int n, m, mod;
  18. int SizeS;
  19. string s;
  20.  
  21. void buildKmp(const string &s)
  22. {
  23.     int n = s.size();
  24.     for(int i = 1; i < n; i++)
  25.     {
  26.         int j = lps[i - 1];
  27.         while(j > 0 && s[j] != s[i])
  28.             j = lps[j - 1];
  29.         if(s[i] == s[j])
  30.             j++;
  31.         lps[i] = j;
  32.     }
  33. }
  34.  
  35. int dp(int i, int j, int kmp)
  36. {
  37.     if(i > m || j > n) 
  38.         return 0; // nếu đi ra khỏi bảng chữ
  39.     if(i == m && j == n) 
  40.         return (kmp == SizeS); // nếu tới ô kết thúc
  41.     if(kmp == SizeS)
  42.          return (dp(i + 1, j, kmp) + dp(i, j + 1, kmp)) % mod; // nếu từ khóa đã xuất hiện thì tìm số cách đi như bình thường
  43.  
  44.     int &res = f[i][j][kmp];
  45.     if(~res) return res;
  46.  
  47.     res = 0;
  48.     for(int branch = 0; branch <= 1; branch++) // đi xuống hoặc qua phải
  49.     {
  50.         int x = i, y = j;
  51.         if(branch == 0) x++; else y++;
  52.  
  53.         int tmp = kmp; 
  54.         while(tmp > 0 && s[tmp] != a[x][y])
  55.             tmp = lps[tmp - 1];
  56.         if(s[tmp] == a[x][y])
  57.             tmp++;
  58.  
  59.         res = (res + dp(x, y, tmp)) % mod;
  60.     }
  61.     return res;
  62. }
  63.  
  64. void solve()
  65. {
  66.     cin >> m >> n >> mod;
  67.     cin >> s;
  68.     for(int i = 1; i <= m; i++)
  69.         for(int j = 1; j <= n; j++)
  70.             cin >> a[i][j];
  71.  
  72.     SizeS = s.size();
  73.     buildKmp(s);
  74.     memset(f, -1, sizeof f);
  75.     cout << dp(1, 1, a[1][1] == s[0]);
  76. }
  77.  
  78. signed main()
  79. {
  80.     cin.tie(0)->sync_with_stdio(0);
  81.     int t = 1;
  82.     // cin >> t;
  83.     while(t--) solve();
  84.     return 0;
  85. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/QUq8m8
language:
C++14 (clang 8.0)
created:
2 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!