fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define TASK ""
  5.  
  6. using ll = long long;
  7. using pii = pair<int,int>;
  8.  
  9. #define fi first
  10. #define se second
  11. #define pub push_back
  12. #define pob pop_back
  13. #define mpa make_pair
  14.  
  15.  
  16. #define forr(i,l,r) for(int i = (l); i <= (r); ++i)
  17. #define fodd(i,l,r) for(int i = (l); i >= (r); --i)
  18.  
  19. const int MAXN = 300000 + 10;
  20. const int MOD = 1000000007;
  21.  
  22. int n, m, k;
  23. vector<string> luu;
  24.  
  25. struct Node {
  26.     int a[26];
  27.     bool ok;
  28.     Node() {
  29.         ok = false;
  30.         memset(a, 0, sizeof a);
  31.     }
  32. };
  33.  
  34.  
  35. static Node trie[MAXN];
  36. int numNode = 0;
  37.  
  38. void addtrie(const string &s) {
  39.     int id = 0;
  40.     for (char ch : s) {
  41.         int c = ch - 'a';
  42.         if (trie[id].a[c] == 0) trie[id].a[c] = ++numNode;
  43.         id = trie[id].a[c];
  44.     }
  45.     trie[id].ok = true;
  46. }
  47.  
  48. ll modpow(ll a, ll b) {
  49.     ll res = 1;
  50.     while (b) {
  51.         if (b & 1) res = (res * a) % MOD;
  52.         a = (a * a) % MOD;
  53.         b >>= 1;
  54.     }
  55.     return res;
  56. }
  57.  
  58. int sz[MAXN];
  59. ll pw[MAXN];
  60. ll inv[MAXN];
  61. int f[MAXN];
  62. ll dp[MAXN];
  63.  
  64. void dfs(int id, int high) {
  65.     if (trie[id].ok) return;
  66.     int cnt = 0;
  67.     for (int c = 0; c < k; ++c) {
  68.         if (trie[id].a[c] == 0) continue;
  69.         ++cnt;
  70.         dfs(trie[id].a[c], high + 1);
  71.     }
  72.  
  73.     f[high + 1] += (k - cnt);
  74. }
  75.  
  76. int main() {
  77.     ios::sync_with_stdio(false);
  78.     cin.tie(nullptr);
  79.  
  80.     cin >> n >> m >> k;
  81.     luu.reserve(n);
  82.     for (int i = 1; i <= n; ++i) {
  83.         string s; cin >> s;
  84.         luu.pub(s);
  85.     }
  86.     sort(luu.begin(), luu.end());
  87.     luu.resize(unique(luu.begin(), luu.end()) - luu.begin());
  88.  
  89.  
  90.     for (const string &s : luu) addtrie(s);
  91.  
  92.     for (int i = 1; i <= m; ++i) cin >> sz[i];
  93.     sort(sz + 1, sz + m + 1);
  94.  
  95.     pw[0] = 1;
  96.     for (int i = 1; i < MAXN; ++i) pw[i] = (1ll * k * pw[i - 1]) % MOD;
  97.  
  98.  
  99.     inv[MAXN - 1] = modpow(pw[MAXN - 1], MOD - 2);
  100.     for (int i = MAXN - 1; i >= 1; --i) inv[i - 1] = (inv[i] * k) % MOD;
  101.  
  102.     dfs(0, 0);
  103.  
  104.     dp[0] = 0;
  105.     for (int i = 1; i < MAXN; ++i) {
  106.         dp[i] = ( (dp[i - 1] * k) % MOD + f[i] ) % MOD;
  107.     }
  108.  
  109.     ll ans = 1;
  110.     ll sum = 0;
  111.     for (int i = 1; i <= m; ++i) {
  112.         int len = sz[i];
  113.         ll cam = (pw[len] * sum) % MOD;
  114.         ll res = (dp[len] - cam + MOD) % MOD;
  115.         ans = (ans * res) % MOD;
  116.         sum += inv[len];
  117.         if (sum >= MOD) sum -= MOD;
  118.     }
  119.  
  120.     cout << ans << '\n';
  121.     return 0;
  122. }
  123.  
Success #stdin #stdout 0.02s 44444KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/nrszOc
language:
C++14 (clang 8.0)
created:
16 hours 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!