103 . DE 字串

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

90.0% (9/10)

Submission's AC Ratio

69.6% (39/56)

Tags

ioicamp ioicamp-2023

Description

2020 年 3 月，隨著 COVID-19 疫情的爆發，其他種類的病毒也在同時蔓延，其中有一種非常可怕的病毒稱為 DE 病毒，被感染到的患者幾乎無法痊癒，終身都會有後遺症。感染 DE 病毒最常見的症狀就是在講數字時會帶有一串特殊的數碼字串，這種字串被稱為DE語。

一般來說，要檢測一個人是否感染 DE 病毒，會讓他隨機講一段數字，然後檢測這段數字中是否有 DE 語作為其子字串。然而健康的人也有可能因為碰巧講出 DE 語，所以我們想知道某種「偽陽性」的機率：假設一個健康的人講了一串 $n$ 個數碼所形成的字串，其中每個字元 $0$ 到 $9$ 都各有 $\frac{1}{10}$ 的機率被講到，而且互相獨立，求一個健康的人碰巧講出 DE 語的機率。

Input Format

第一行有一個整數 $m$，代表 DE 語的長度。

第二行有一個字串 $s$，為 DE 語。

第三行有一個整數 $q$，代表有 $q$ 筆詢問。

接下來有 $q$ 行，每一行代表一個詢問。每個詢問有一個整數 $n$，問一個正常人如題敘所述隨機講一段長度是 $n$ 的數字，有多少的機率會講出 DE 語。

  • $1\leq m=|s|\leq9$
  • $\forall1\leq i\leq m,\ s[i]\in\lbrace 0, 1, \dots, 9 \rbrace$
  • $1\leq q\leq 4 \times 10^ 4$
  • $1\leq n\leq10^ {18}$

Output Format

對於每筆詢問，如果機率的最簡分數型式是 $\frac{p}{q}$，請輸出 $p \cdot q ^ {998244351}$ 除以 $998244353$ 的餘數。

Sample Input 1

9
777771449
4
7
14
49
777771449

Sample Output 1

0
922086193
474948367
719343586

Hints

Problem Source

IOICamp 2023 Day2 pC

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 1~24 $n\leq 1000, q\leq 10$ 10
3 0~48 $n\leq 10^ {18}, q\leq 100$ 80
4 0~72 無特別限制 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 3 4
1 1000 262144 65536 2 3 4
2 1000 262144 65536 2 3 4
3 1000 262144 65536 2 3 4
4 1000 262144 65536 2 3 4
5 1000 262144 65536 2 3 4
6 1000 262144 65536 2 3 4
7 1000 262144 65536 2 3 4
8 1000 262144 65536 2 3 4
9 1000 262144 65536 2 3 4
10 1000 262144 65536 2 3 4
11 1000 262144 65536 2 3 4
12 1000 262144 65536 2 3 4
13 1000 262144 65536 2 3 4
14 1000 262144 65536 2 3 4
15 1000 262144 65536 2 3 4
16 1000 262144 65536 2 3 4
17 1000 262144 65536 2 3 4
18 1000 262144 65536 2 3 4
19 1000 262144 65536 2 3 4
20 1000 262144 65536 2 3 4
21 1000 262144 65536 2 3 4
22 1000 262144 65536 2 3 4
23 1000 262144 65536 2 3 4
24 1000 262144 65536 2 3 4
25 1000 262144 65536 3 4
26 1000 262144 65536 3 4
27 1000 262144 65536 3 4
28 1000 262144 65536 3 4
29 1000 262144 65536 3 4
30 1000 262144 65536 3 4
31 1000 262144 65536 3 4
32 1000 262144 65536 3 4
33 1000 262144 65536 3 4
34 1000 262144 65536 3 4
35 1000 262144 65536 3 4
36 1000 262144 65536 3 4
37 1000 262144 65536 3 4
38 1000 262144 65536 3 4
39 1000 262144 65536 3 4
40 1000 262144 65536 3 4
41 1000 262144 65536 3 4
42 1000 262144 65536 3 4
43 1000 262144 65536 3 4
44 1000 262144 65536 3 4
45 1000 262144 65536 3 4
46 1000 262144 65536 3 4
47 1000 262144 65536 3 4
48 1000 262144 65536 3 4
49 1000 262144 65536 4
50 1000 262144 65536 4
51 1000 262144 65536 4
52 1000 262144 65536 4
53 1000 262144 65536 4
54 1000 262144 65536 4
55 1000 262144 65536 4
56 1000 262144 65536 4
57 1000 262144 65536 4
58 1000 262144 65536 4
59 1000 262144 65536 4
60 1000 262144 65536 4
61 1000 262144 65536 4
62 1000 262144 65536 4
63 1000 262144 65536 4
64 1000 262144 65536 4
65 1000 262144 65536 4
66 1000 262144 65536 4
67 1000 262144 65536 4
68 1000 262144 65536 4
69 1000 262144 65536 4
70 1000 262144 65536 4
71 1000 262144 65536 4
72 1000 262144 65536 4
Submit
Back to Top