给定$m$个字符以及他们的权值$v[i]$。

再给定一个长度为$n$字符串$s$，让你求所有长度为$n+k$的字符串的权值乘积总和（删除$k$个后为$s$)

$abc$->$aabc$，可以有两种添加方式，若我们每次$i$的右边，即可添加的字符为$m-1$个,权值合$\sum_{s_i!=j}v_j$.

问题就转化为$n+1$种背包,每个背包权值为$w_i$,选择$k$个背包求权值总和.

$\rightarrow (1+w_1x+w_1^2x^2+)…(1+w_ix+w_i^2x^2)->\prod \frac{1}{1-w_ix}$

可以分母分治$NTT$，然后取个倒数。$(NTT)真的神奇$。

注意

注意控制$NTT$边界，不然复杂度会蝴蝶效应般增大。

代码

```c++

include

using namespace std;
typedef long long ll;

define pii pair

define mk make_pair

const int N = (1 << 19) + 10;
const int mod = 998244353;
const int P = 998244353, gi = 3;
// const double pi = acos(-1.0);
int inc(int x, int y) { return (x + y >= mod) ? (x + y - mod) : (x + y); }
int del(int x, int y) { return (x - y < 0) ? (x - y + mod) : (x - y); }
int read()
{
int x = 0, f = 1;
char c = getchar();
while (c < ‘0’ || c > ‘9’)
{
if (c == ‘-‘)
f = -1;
c = getchar();
}
while (c >= ‘0’ && c <= ‘9’)
x = (x << 1) + (x << 3) + c - ‘0’, c = getchar();
return x * f;
}

int qpow(int a, int x, int mo)
{
int res = 1;
while (x)
{
if (x & 1)
res = 1ll res a % mo;
x >>= 1;
a = 1ll a a % mo;
}
return res;
}

int rev[N];
void NTT(int A, int n, int inv)
{
for (int i = 0; i < n; i++)
if (i < rev[i])
swap(A[i], A[rev[i]]);
for (int l = 1; l < n; l <<= 1)
{
int tt = qpow(gi, (P - 1) / (l << 1), P);
int temp = (inv == 1 ? tt : qpow(tt, P - 2, P));
for (int i = 0; i < n; i += (l << 1))
{
int omega = 1;
for (int j = 0; j < l; j++, omega = 1ll omega temp % P)
{
int x = A[i + j], y = 1ll omega A[i + j + l] % P;
A[i + j] = inc(x, y);
A[i + j + l] = del(x, y);
}
}
}
int invv = qpow(n, P - 2, P);
if (inv == -1)
for (int i = 0; i < n; i++)
A[i] = 1ll A[i] * invv % P;
}

int Inv2;
int C[N], D[N];
int Ployinit(int n, int m)
{
int ML = 1, bit = 0;
while (ML < n + m - 1)
ML <<= 1, bit++;
return ML;
}
void NTTX(int a, int n, int b, int m)
{
int ML = 1, bit = 0;
while (ML < n + m - 1)
ML <<= 1, bit++;
for (int i = 0; i < ML; i++)
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
NTT(a, ML, 1);
NTT(b, ML, 1);
for (int i = 0; i < ML; i++)
a[i] = 1ll a[i] b[i] % P;
NTT(a, ML, -1);
}
void Finv(int a, int b, int n)
{
b[0] = qpow(a[0], P - 2, P);
int len, ML;
memset(C, 0, sizeof(C));
memset(D, 0, sizeof(D));
for (len = 1; len < (n << 1); len <<= 1)
{
ML = len << 1;
for (int i = 0; i < len; i++)
C[i] = a[i], D[i] = b[i];
for (int i = 0; i < ML; i++)
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? len : 0);
NTT(C, ML, 1), NTT(D, ML, 1);
for (int i = 0; i < ML; i++)
b[i] = ((2ll - 1ll C[i] D[i] % P) * D[i] % P + P) % P;
NTT(b, ML, -1);
for (int i = len; i < ML; i++)
b[i] = 0;
}

for (int i = n; i < len; i++)
    b[i] = 0;

}
int cnt = 0;

vector g[N];
int p[N], v[N];
int k;
int p1[N], p2[N];
int solve(int l, int r)
{
if (l == r)
return l;
int mid = (l + r) >> 1;
int pa = solve(l, mid);
int pb = solve(mid + 1, r);
int len1 = g[pa].size();
int len2 = g[pb].size();
int ML = Ployinit(len1, len2);
for (int i = 0; i < ML; i++)
p1[i] = p2[i] = 0;
for (int i = 0; i < len1; i++)
p1[i] = g[pa][i];
for (int i = 0; i < len2; i++)
p2[i] = g[pb][i];

NTTX(p1, len1, p2, len2);

g[pa].clear();
int li = min(k + 1, len1 + len2 - 1);
for (int i = 0; i < li; i++)
    g[pa].push_back(p1[i]);
return pa;

}

int main()
{
int n, m;
while (scanf(“%d %d %d”, &n, &m, &k))
{
if (n + m + k <= 0)
break;

    int sum = 0;

    for (int i = 1; i <= n; i++)
        p[i] = read();
    for (int i = 1; i <= m; i++)
        v[i] = read(), sum = inc(sum, v[i]);
    cnt = n;
    for (int i = 0; i <= n; i++)
    {
        g[i].clear();
        g[i].push_back(1);
        g[i].push_back(del(mod, del(sum, v[p[i]])));
    }
    int pa = solve(0, n);
    memset(p1, 0, sizeof(p1));
    memset(p2, 0, sizeof(p2));
    g[pa].resize(k + 1);
    int len1 = g[pa].size();

    for (int i = 0; i < len1; i++)
        p1[i] = g[pa][i];

    Finv(p1, p2, k + 1);
    int ans = 0;

    for (int i = 0; i <= k; i++)
        ans = inc(ans, p2[i]);
    for (int i = 1; i <= n; i++)
        ans = 1ll * ans * v[p[i]] % mod;

    printf("%d\n", ans);
}

return 0;

}