qoj8306

发表于 更新于 本文字数： 3.2k 阅读时长 ≈ 3 分钟

给定 nn 个长度为 mm 的串 TiT_i，对于一个串 SS，每次在 SS 后面以 pip_i 概率加一个字符 ii，包含一个 TjT_j 则停止，给出一个串 RR，求所有 S=R[1,i]S=R[1,i] 时，停止的期望长度。

n≤100,nm≤10000n\le 100,nm\le 10000 。

PGF 倒闭了！！！

SS 为空的时候有PGF经典做法。

场上想了半天，感觉 PGF 完全不可做。

直接考虑最朴素的，n=1n=1 咋做，可以在 KMP 自动机上面列方程然后高斯消元。

去考虑主元法，设空串值为 xx，然后考虑每次已知一个前缀表出的值，然后一个点的方程只和前面的点与后面一个点有关，因此后面一个点也可以用 xx 表达了，因此可以解出。

现在 nn 比较大了，建出 AC 自动机，还是要主元，但是可能有多个儿子，因此考虑剖分一下，变成若干条链，每条链的链顶是一个主元然后去消。

容易发现主元数量为 nn，因此复杂度为 O(nm+n3)\mathcal{O}(nm+n^3) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <bits/stdc++.h>
#define For(i, l, r) for (int i = l; i <= r; i++)
#define Rep(i, r, l) for (int i = r; i >= l; i--)
#define V vector
#define Vi vector<int>
#define Int pair<int, int>
#define fi first
#define se second
#define sz(a) ((int)a.size())
#define pb push_back
using namespace std;

const int P = 1e9 + 7;
int kuai(int a, int b) {
  int ans = 1;
  for (; b; b >>= 1, a = 1ll * a * a % P)
    if (b & 1) ans = 1ll * ans * a % P;
  return ans;
}

const int N = 1e4 + 5;
int tr[N][30], en[N], tot = 0, nex[N];
struct Ace_taffy {
  void add(string &s) {
    int t = 0;
    for (char c : s) {
      if (!tr[t][c - 'a']) tr[t][c - 'a'] = ++tot;
      t = tr[t][c - 'a'];
    }
    en[t] = 1;
  }
  void build() {
    queue<int> q;
    q.push(0);
    for (; !q.empty(); q.pop()) {
      int x = q.front(), t = nex[x];
      For(i, 0, 26) {
        int y = tr[x][i];
        if (!y)
          tr[x][i] = tr[t][i];
        else
          nex[y] = x ? tr[t][i] : 0, q.push(y);
      }
    }
  }
};

int main() {
  ios::sync_with_stdio(0);

  int n, m, K;
  cin >> n >> m >> K;

  int I = kuai(100, P - 2);
  Vi p(K + 5), Ip(K + 5);
  For(i, 0, K - 1) {
    cin >> p[i], p[i] = 1ll * p[i] * I % P;
    Ip[i] = kuai(p[i], P - 2);
  }

  V<string> S(n + 5);
  For(i, 1, n) cin >> S[i];
  string R;
  cin >> R;
  if (K == 1) {
    For(i, 1, sz(R)) cout << max(m, i) << '\n';
    return 0;
  }

  Ace_taffy G;
  For(i, 1, n) G.add(S[i]);
  G.build();

  int T = tot, D = 1, B = 0;
  V<Vi> c(T + 5, Vi(n + 5)), d(n + 5, Vi(n + 5));
  c[0][1] = 1;

  queue<int> q;
  Vi vis(T + 5);
  q.push(0), vis[0] = 1;
  for (; !q.empty(); q.pop()) {
    int x = q.front();
    Vi sn, oth;
    For(i, 0, K - 1) if (!vis[tr[x][i]]) vis[tr[x][i]] = 1, sn.pb(i);
    else oth.pb(i);

    if (!sz(sn))
      d[++B] = c[x], d[B][0] = P - d[B][0];
    else {
      For(i, 1, sz(sn) - 1) c[tr[x][sn[i]]][++D] = 1;

      int y = tr[x][sn[0]];
      For(j, 0, D) c[y][j] = c[x][j];
      c[y][0] = (c[y][0] + P - 1) % P;

      For(i, 0, sz(oth) - 1) For(j, 0, D) c[y][j] =
          (c[y][j] - 1ll * p[oth[i]] * c[tr[x][oth[i]]][j] % P + P) % P;
      For(i, 1, sz(sn) - 1) For(j, 0, D) c[y][j] =
          (c[y][j] - 1ll * p[sn[i]] * c[tr[x][sn[i]]][j] % P + P) % P;
      For(j, 0, D) c[y][j] = 1ll * c[y][j] * Ip[sn[0]] % P;

      for (int i : sn) q.push(tr[x][i]);
    }
  }

  For(i, 1, B) {
    For(j, i, B) if (d[j][i]) {
      swap(d[i], d[j]);
      break;
    }
    int Inv = kuai(d[i][i], P - 2);
    For(j, 1, B) if (i != j) {
      int div = 1ll * d[j][i] * Inv % P;
      For(k, 0, B) d[j][k] = (d[j][k] - 1ll * div * d[i][k] % P + P) % P;
    }
  }

  Vi res(B + 5);
  For(i, 1, B) res[i] = 1ll * d[i][0] * kuai(d[i][i], P - 2) % P;
  res[0] = 1;

  Vi val(T + 5);
  For(i, 0, T) For(j, 0, B) val[i] = (val[i] + 1ll * res[j] * c[i][j] % P) % P;

  int t = 0, g = 0, ff = 0;
  for (char c : R) {
    t = tr[t][c - 'a'];
    g++;
    if (en[t]) ff = 1;
    if (ff)
      cout << g << '\n';
    else
      cout << (g + val[t]) % P << '\n';
  }
}