fork download
copy 
  1. // ROOT : DRAGON3012009 : WA in Real Life
  2. #include <bits/stdc++.h>
  3. #define FOR(i,l,r) for(int i = l ; i <= r ; i ++)
  4. #define FORD(i,r,l) for(int i = r ; i >= l ; i --)
  5. #define REP(i, a ) for(int i = 0 ; i < a ; i ++ )
  6. #define compare(v) sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end());
  7. #define ll long long
  8. #define el "\n"
  9. #define fi first
  10. #define se second
  11. #define _ROOT_ int main()
  12. #define MAXN 205
  13. #define ALPHA 26
  14. #define Bit(i) (1LL << i )
  15. #define INF (1ll<<30)
  16. #define NAME "file"
  17. #define debug(a) cout << #a << " = " << a << endl;
  18. using namespace std;
  19.  
  20. ll n, m, q, len, M ;
  21. ll dp[MAXN][MAXN][MAXN ] ;
  22. ll nxtA[MAXN][ALPHA] ;
  23. ll nxtB[MAXN][ALPHA] ;
  24. string a, b ;
  25.  
  26. ll Power(ll a, ll b ) {
  27.     ll res = 1;
  28.     while(b) {
  29.         if(b&1) res = a*res%M;
  30.         b>>=1;
  31.         a=a*a%M;
  32.     }
  33.     return res;
  34. }
  35. ll add(ll a, ll b ) {
  36.     return a + b >= M ? a + b - M : a + b;
  37. }
  38. ll mul(ll a, ll b )  {
  39.     return 1LL * (a%M) * (b%M) % M;
  40. }
  41. ll sub(ll a, ll b ) {
  42.     return a - b < 0 ? a - b + M : a - b;
  43. }
  44. ll divi(ll a, ll b) {
  45.     return 1LL * a * Power(b, M - 2 ) % M;
  46. }
  47.  
  48. ll DP(ll pos, ll khopA, ll khopB ) {
  49.     if(pos > len ) {
  50.         return khopA <= n && khopB > m ;
  51.     }
  52.     ll &cur = dp[pos][khopA][khopB ] ;
  53.     if(cur != - 1 ) return cur ;
  54.     cur = 0 ;
  55.  
  56.     REP(c, ALPHA ) {
  57.         ll nxt_A = nxtA[khopA + 1 ][c ] ;
  58.         ll nxt_B = nxtB[khopB + 1 ][c] ;
  59.         if(khopB > m) nxt_B = khopB ;
  60.         if(khopA > n) nxt_A = khopA ;
  61.  
  62.         cur = add(cur,  DP(pos + 1, nxt_A, nxt_B ) ) ;
  63.     }
  64.     return cur ;
  65. }
  66.  
  67. void init() {
  68.     cin >> q >> len >> M ;
  69.     cin >> a >> b ;
  70.     n = a.size() ;
  71.     m = b.size() ;
  72.     a = " " + a ;
  73.     b = " " + b ;
  74.     REP(i, ALPHA ) {
  75.         nxtA[n + 1][i] = n + 1 ;
  76.         nxtB[m + 1][i] = m + 1 ;
  77.     }
  78.     FORD(i, n, 1 ) {
  79.         REP(j, ALPHA ) {
  80.             if(a[i] - 'a' == j) nxtA[i][j] = i ;
  81.             else nxtA[i][j] = nxtA[i + 1][j] ;
  82.         }
  83.     }
  84.     FORD(i, m, 1 ) {
  85.         REP(j, ALPHA ) {
  86.             if(b[i] - 'a' == j) nxtB[i][j] = i ;
  87.             else nxtB[i][j] = nxtB[i + 1][j] ;
  88.         }
  89.     }
  90. }
  91.  
  92. bool checkTrue(string &tmp ) {
  93.     tmp = " " + tmp ;
  94.     ll ptr = 1 ;
  95.     FOR(i, 1, n ) if(a[i] == tmp[ptr ] ) ptr ++ ;
  96.     if(ptr <= len ) return false ;
  97.     ptr = 1 ;
  98.     FOR(i, 1,  m ) if(b[i] == tmp[ptr ] ) ptr ++ ;
  99.     if(ptr > len ) return false ;
  100.     return true ;
  101. }
  102.  
  103. void solve() {
  104.     memset(dp , -1 , sizeof dp ) ;
  105.     DP(1 , 0 , 0 ) ;
  106.  
  107.     FOR(cnt, 1, q ) {
  108.         string x ;
  109.         cin >> x ;
  110.         if(!checkTrue(x)) {
  111.             cout << -1 << el ;
  112.             continue ;
  113.         }
  114.         ll khopA = 0, khopB = 0 ;
  115.         ll ans = 1 ;
  116.  
  117.         FOR(i, 1,  len ) {
  118.             REP(c, x[i] - 'a') {
  119.                 ll nxt_A = nxtA[khopA + 1 ][c ] ;
  120.                 ll nxt_B = nxtB[khopB + 1 ][c] ;
  121.                 if(khopB > m) nxt_B = khopB ;
  122.                 if(khopA > n) nxt_A = khopA ;
  123.                 ans = add(ans, DP(i + 1, nxt_A, nxt_B )) ;
  124.             }
  125.             ll nxt_A = nxtA[khopA + 1 ][x[i] - 'a' ] ;
  126.             ll nxt_B = nxtB[khopB + 1 ][x[i] - 'a' ] ;
  127.             if(khopB > m) nxt_B = khopB ;
  128.             if(khopA > n) nxt_A = khopA ;
  129.             khopA = nxt_A, khopB = nxt_B ;
  130.         }
  131.         cout << ans << el ;
  132.     }
  133. }
  134.  
  135. _ROOT_ {
  136.     // freopen(NAME".inp" , "r" , stdin);
  137.     // freopen(NAME".out" , "w", stdout) ;
  138.     ios_base::sync_with_stdio(0);
  139.     cin.tie(0);
  140.     cout.tie(0);
  141.     int t = 1; // cin >> t ;
  142.     while(t--) {
  143.         init();
  144.         solve();
  145.     }
  146.     return (0&0);
  147. }
  148.  
Success #stdin #stdout 0.01s 70928KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/OtqR8m
language:
C++14 (gcc 8.3)
created:
1 day 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!