fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. #define FOR(i, a, b) for (int i = a; i <= b; ++i)
  4. #define FORD(i, a, b) for (int i = a; i >= b; --i)
  5. #define ll long long
  6.  
  7. using namespace std;
  8.  
  9. const int N = 1e6 + 5;
  10. const ll mod = 1e9 + 7;
  11. int a[N], n, m, k;
  12. ll cnt_len[N], ans = 1; 
  13.  
  14. struct Node {
  15.     Node *child[26];
  16.     bool last;
  17.     Node() {
  18.         FOR(i, 0, 25) child[i] = NULL;
  19.         last = 0;
  20.     }
  21. };
  22.  
  23. Node *root = new Node();
  24.  
  25. void add_word(string s) {
  26.     Node *p = root;
  27.     for (char c : s) {
  28.         int x = c - 'a';
  29.         if (p->child[x] == NULL) p->child[x] = new Node();
  30.         p = p->child[x];
  31.     }
  32.     p->last = 1;
  33. }
  34.  
  35. void addmod(ll &a, const ll &b) {
  36.     a += b;
  37.     if (a >= mod) a -= mod;
  38. }
  39.  
  40. void nhap() {
  41.     cin >> n >> m >> k;
  42.     FOR(i, 1, n) {
  43.         string s;
  44.         cin >> s;
  45.         add_word(s);
  46.     }
  47.     FOR(i, 1, m) cin >> a[i];
  48.     sort(a + 1, a + 1 + m);
  49. }
  50.  
  51. void dfs(Node *p, int len) {
  52.     if (p->last) return;
  53.  
  54.     int empty_cnt = 0;
  55.     FOR(i, 0, k - 1) {
  56.         if (p->child[i] == NULL) ++empty_cnt;
  57.         else dfs(p->child[i], len + 1);
  58.     }
  59.  
  60.     addmod(cnt_len[len], empty_cnt);
  61. }
  62.  
  63. void giai() {
  64.     dfs(root, 1);
  65.  
  66.     int pos = 1;
  67.     FOR(i, 1, m) {
  68.         while (pos <= a[i]) {
  69.             cnt_len[pos] = (cnt_len[pos] + cnt_len[pos - 1] * k) % mod;
  70.             ++pos;
  71.         }
  72.         ans = ans * cnt_len[a[i]] % mod;
  73.  
  74.         --cnt_len[a[i]];
  75.         if (cnt_len[a[i]] < 0) cnt_len[a[i]] += mod;
  76.     }
  77.  
  78.     cout << ans;
  79. }
  80.  
  81. int main() {
  82.     ios_base::sync_with_stdio(0);
  83.     cin.tie(0);
  84.     cout.tie(0);
  85.  
  86.     #define name "test"
  87.  
  88.     if (fopen(name ".inp", "r")) {
  89.         freopen(name ".inp", "r", stdin);
  90.         freopen(name ".out", "w", stdout);
  91.     }
  92.  
  93.     nhap();
  94.     giai();
  95.  
  96.     return 0;
  97. }
  98.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
1
https://ideone.com/wCm5jN
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!