seuOJ458 - 小Q的机器

题目描述

小Q有一个神奇的机器，可以随机生成某个长度的字符串（包括长度为00的空串）。字符串的不同位之间相互独立，同一字符在任一位上出现的概率都是相同的。

小Q发现了一个自己很喜欢的字符串SS，他希望知道如果他让机器生成一个长度为kk的字符串，SS是该字符串的子序列的概率是多少。

一个字符串的子序列是指从该字符串中取部分字符（可以全取或全不取），取出来的字符按在原串中的顺序排列而成的字符序列。如空串、”aba”、”aac”、”ababc”都是”ababc”的子序列，而”cab”则不是。

输入格式

第一行2626个非负数，表示从’a’到’z’每个字符的权重，即输入weight[‘a’..’z’](0≤weight[i]≤1000)weight[‘a’..’z’](0 \le weight[i] \le 1000)，字符chch在任一位上出现的概率为

weight[ch]∑i=′a′i=′z′weight[i]\frac{weight[ch]}{\sum_{i='a'}^{i='z'}weight[i]}

第二行一个字符串 S(1≤∣S∣≤100)S(1\le |S| \le 100)。

第三行一个正整数 T(1≤T≤100)T(1\le T \le 100)，表示数据组数。

接下来TT行，每一个一个正整数 k(0≤k<260)k(0\le k < 2^{60})，表示机器生成的字符串长度。

保证至少有一个weight[i]weight[i]不为00。

输出格式

TT行，每行一个正整数，表示SS是该字符串的子序列的概率，对998244353998244353取模的结果。

可以证明答案一定可以表示成 qp\frac{q}{p}，其中qq为非负整数，pp为正整数，且存在一个正整数p(−1)p^{(-1)}，使得 p(−1)×p≡1 mod 998244353p^{(-1)}×p≡1\ mod\ 998244353，即pp在模998244353998244353下一定存在逆元，你只需输出q×p(−1)q×p^{(-1)}模998244353998244353的值即可。

样例

输入样例：

30 40 30 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
abc
6
0
1
2
3
4
5

输出样例：

0
0
0
387318809
163712074
688748674

样例解释：
aa在每一位上出现的概率为0.30.3，bb为0.40.4，cc为0.30.3，其余字符不可能出现。
k=0k=0时，只能生成空串，k=1,2k=1,2时，长度小于33，不可能包含子序列”abc”。
k=3k=3时，长度为33的串只有abc，概率为0.3⋅0.4⋅0.3=0.0360.3·0.4·0.3=0.036，模998244353998244353为387318809387318809。
k=4k=4时，长度为44的串中abc*,ab*c,a*bc,*abc符合条件，计算得概率为0.10800.1080，模998244353998244353为163712074163712074。
k=5k=5时，概率为0.204120.20412，模998244353998244353为688748674688748674。