Advertisement
at3107

Untitled

Aug 17th, 2020
2,240
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.77 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int         long long
  4. #define ull         unsigned long long
  5. #define ll          long long
  6. #define MM          1000000007
  7. #define N           100005
  8. #define pb          push_back
  9. #define p_q         priority_queue
  10. #define pii         pair<ll,ll>
  11. #define vi          vector<ll>
  12. #define vii         vector<pii>
  13. #define mi          map<ll,ll>
  14. #define mii         map<pii,ll>
  15. #define all(a)      (a).begin(),(a).end()
  16. #define sz(x)       (ll)x.size()
  17. #define endl        '\n'
  18. #define Endl        '\n'
  19. #define gcd(a,b)    __gcd((a),(b))
  20. #define lcm(a,b)    ((a)*(b)) / gcd((a),(b))
  21. #define ios         ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  22. #define mp          make_pair
  23. #define lb          lower_bound
  24. #define ub          upper_bound
  25. #define F           first
  26. #define S           second
  27. #define rep(i, begin, end) for(int i=begin;i<end;i++)
  28. #define repr(i,begin,end) for(int i=end-1;i>=begin;i--)
  29. #define ini(a,n,b)  for(ll int i=0;i<n;i++) a[i]=0;
  30. #define cset(a)     __builtin_popcountll(a)
  31. #define hell        (ull)1e9
  32. #define re          resize
  33.  
  34.  int dp[1000][1000],n;
  35.  vector<int> inde[26];
  36.  string t;
  37.  
  38.  int fun(int ind,int prev)
  39.  {
  40.      if(ind==sz(t)) return 1;
  41.      if(dp[ind][prev]!=-1) return dp[ind][prev];
  42.      int c=t[ind]-'a';
  43.      int ans=0;
  44.      for(int i:inde[c])
  45.      {
  46.          if(i>prev)
  47.          {
  48.              ans=(ans+fun(ind+1,i))%MM;
  49.          }
  50.      }
  51.      return dp[ind][prev]=ans;
  52.  }
  53.  
  54. signed main(void)
  55. {ios
  56.     int TESTS=1;
  57.     //cin>>TESTS;
  58.     while(TESTS--)
  59.     {
  60.         cin>>n;
  61.         rep(i,0,n)
  62.         {
  63.             string s;
  64.             cin>>s;
  65.             for(int j=0;j<s.size();j++) inde[s[j]-'a'].pb(j);
  66.         }
  67.         cin>>t;
  68.         memset(dp,-1,sizeof(dp));
  69.         int ans=0;
  70.         int c=t[0]-'a';
  71.         for(int i:inde[c])
  72.         {
  73.             ans=(ans+fun(1,i))%MM;
  74.         }
  75.         cout<<ans;
  76.     }
  77. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement