fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef unsigned long long ull;
  7.  
  8. #define MASK(i) (1LL << (i))
  9. #define GETBIT(mask, i) (((mask) >> (i)) & 1)
  10. #define ALL(v) (v).begin(), (v).end()
  11.  
  12. ll max(ll a, ll b){return (a > b) ? a : b;}
  13. ll min(ll a, ll b){return (a < b) ? a : b;}
  14.  
  15. ll LASTBIT(ll mask){return (mask) & (-mask);}
  16. long pop_cnt(ll mask){return __builtin_popcountll(mask);}
  17. long ctz(ll mask){return __builtin_ctzll(mask);}
  18. long clz(ll mask){return __builtin_clzll(mask);}
  19. long logOf(ll mask){return 63 - clz(mask);}
  20.  
  21. mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
  22.  
  23. template <class T1, class T2>
  24.     bool maximize(T1 &a, T2 b){
  25.         if (a < b) {a = b; return true;}
  26.         return false;
  27.     }
  28.  
  29. template <class T1, class T2>
  30.     bool minimize(T1 &a, T2 b){
  31.         if (a > b) {a = b; return true;}
  32.         return false;
  33.     }
  34.  
  35. template <class T>
  36.     void printArr(T& container, char separator = ' ', char finish = '\n'){
  37.         for(auto item: container) cout << item << separator;
  38.         cout << finish;
  39.     }
  40.  
  41. template <class T>
  42.     void compress(vector<T> &a){
  43.         sort(ALL(a));
  44.         a.resize(unique(ALL(a)) - a.begin());
  45.     }
  46.  
  47. const long MOD = 1e9 + 7;
  48.  
  49. const long MAX = 1e5 + 9;
  50.  
  51. const long BASE = 307;
  52. const long MOD1 = 1e9 + 7;
  53. const long MOD2 = 1e9 + 9;
  54.  
  55. ll pow1[MAX], pow2[MAX];
  56.  
  57. void prepare(){
  58.     pow1[0] = pow2[0] = 1;
  59.     for(long i = 1; i<MAX; ++i){
  60.         pow1[i] = pow1[i-1] * BASE % MOD1;
  61.         pow2[i] = pow2[i-1] * BASE % MOD2;
  62.     }
  63. }
  64.  
  65. struct Hash{
  66.     long n;
  67.     vector<ll> hash1, hash2;
  68.  
  69.     Hash(string s){
  70.         n = s.size();
  71.         hash1.resize(n+1); hash2.resize(n+1);
  72.         for(long i = 1; i<=n; ++i){
  73.             hash1[i] = (hash1[i-1] + pow1[i-1] * s[i-1]) % MOD1;
  74.             hash2[i] = (hash2[i-1] + pow2[i-1] * s[i-1]) % MOD2;
  75.         }
  76.     }
  77.  
  78.     ll get1(long l, long r){
  79.         return (hash1[r] - hash1[l - 1] + MOD1) * pow1[MAX - l] % MOD1;
  80.     }
  81.  
  82.     ll get2(long l, long r){
  83.         return (hash2[r] - hash2[l - 1] + MOD2) * pow2[MAX - l] % MOD2;
  84.     }
  85.  
  86.     ll getCode(long l, long r){
  87.         return MOD2 * get1(l, r) + get2(l, r);
  88.     }
  89. };
  90. int main(void){
  91.     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  92.  
  93.     prepare();
  94.  
  95.     long n;
  96.     cin >> n;
  97.  
  98.     vector<string> a(n);
  99.     vector<long> len(n);
  100.     for(long i = 0; i<n; ++i){
  101.         cin >> a[i];
  102.         len[i] = a[i].size();
  103.     }
  104.  
  105.     compress(len);
  106.  
  107.     long k = len.size();
  108.     vector<vector<ll>> hashCode(k);
  109.     for(long i = 0; i<n; ++i){
  110.         Hash x(a[i]);
  111.         long idx = lower_bound(ALL(len), a[i].size()) - len.begin();
  112.         hashCode[idx].push_back(x.getCode(1, a[i].size()));
  113.     }
  114.  
  115.     for(long i = 0; i<k; ++i)
  116.         sort(ALL(hashCode[i]));
  117.  
  118.     string s; cin >> s;
  119.  
  120.     long m = s.size();
  121.     vector<ll> dp(m + 1);
  122.     dp[0] = 1;
  123.     Hash x(s);
  124.     for(long i = 0; i<m; ++i)
  125.     for(long j = 0; j<k; ++j){
  126.         if (i + len[j] > m) break;
  127.         ll hentaiCode = x.getCode(i + 1, i + len[j]);
  128.         long cnt = upper_bound(ALL(hashCode[j]), hentaiCode) - lower_bound(ALL(hashCode[j]), hentaiCode);
  129.         dp[i + len[j]] += dp[i] * cnt;
  130.         if (dp[i + len[j]] >= MOD) dp[i + len[j]] %= MOD;
  131.     }
  132.  
  133.     cout << dp[m] << "\n";
  134.  
  135.     return 0;
  136. }
Success #stdin #stdout 0.01s 5544KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/E70kZl
language:
C++ (gcc 8.3)
created:
1 year 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!