30 . 都變成 1

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

abcabcabc

User's AC Ratio

84.6% (11/13)

Submission's AC Ratio

42.4% (14/33)

Tags

ioicamp ioicamp-2024

Description

給定一個長度為 $N$ 的 01 字串 $A_i$，你將對此字串做恰好 $Q$ 次操作。
在一次操作之中，你必須先選擇兩個正整數 $l, r(1 \le l \le r \le N)$，之後將 $A_l, A_{l+1}, \ldots, A_r$ 都改成 $1$。
也就是說如果原本字串是 0110101，在選擇 $l = 3, r = 6$ 之後，字串會變成 0111111。

排列組合大魔王蛋餅現在想要知道，總共有多少種方法可以讓字串經過 $Q$ 次操作後，全部的元素都是 1 呢？

  • 兩組操作方法 $X, Y$ 不一樣若且唯若存在 $i(1 \le i \le Q)$ 使得 $X$ 中的第 $i$ 個操作和 $Y$ 中的第 $i$ 個操作不一樣。
  • 由於答案可能非常大，請輸出答案除以 $998,244,353$ 的餘數。

Input Format

輸入的第一行有兩個正整數 $N, Q$ 意義如題敘。
輸入的第二行有個長度為 $N$ 的 01 字串 $A$。

  • $1 \le N \le 100$
  • $1 \le Q \le 100$
  • $A_i \in \lbrace 0, 1\rbrace$

Output Format

輸出答案除以 $998,244,353$ 的餘數。

Sample Input 1

2 2
00

Sample Output 1

7

Sample Input 2

4 2
0101

Sample Output 2

52

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資。 0
2 0~26 $1 \le N \le 20$ 20
3 0~1, 27~60 $1 \le N, Q \le 50$ 30
4 0~94 無特別限制。 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 2 3 4
1 1000 262144 65536 1 2 3 4
2 1000 262144 65536 2 4
3 1000 262144 65536 2 4
4 1000 262144 65536 2 4
5 1000 262144 65536 2 4
6 1000 262144 65536 2 4
7 1000 262144 65536 2 4
8 1000 262144 65536 2 4
9 1000 262144 65536 2 4
10 1000 262144 65536 2 4
11 1000 262144 65536 2 4
12 1000 262144 65536 2 4
13 1000 262144 65536 2 4
14 1000 262144 65536 2 4
15 1000 262144 65536 2 4
16 1000 262144 65536 2 4
17 1000 262144 65536 2 4
18 1000 262144 65536 2 4
19 1000 262144 65536 2 4
20 1000 262144 65536 2 4
21 1000 262144 65536 2 4
22 1000 262144 65536 2 4
23 1000 262144 65536 2 4
24 1000 262144 65536 2 4
25 1000 262144 65536 2 4
26 1000 262144 65536 2 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 3 4
50 1000 262144 65536 3 4
51 1000 262144 65536 3 4
52 1000 262144 65536 3 4
53 1000 262144 65536 3 4
54 1000 262144 65536 3 4
55 1000 262144 65536 3 4
56 1000 262144 65536 3 4
57 1000 262144 65536 3 4
58 1000 262144 65536 3 4
59 1000 262144 65536 3 4
60 1000 262144 65536 3 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
73 1000 262144 65536 4
74 1000 262144 65536 4
75 1000 262144 65536 4
76 1000 262144 65536 4
77 1000 262144 65536 4
78 1000 262144 65536 4
79 1000 262144 65536 4
80 1000 262144 65536 4
81 1000 262144 65536 4
82 1000 262144 65536 4
83 1000 262144 65536 4
84 1000 262144 65536 4
85 1000 262144 65536 4
86 1000 262144 65536 4
87 1000 262144 65536 4
88 1000 262144 65536 4
89 1000 262144 65536 4
90 1000 262144 65536 4
91 1000 262144 65536 4
92 1000 262144 65536 4
93 1000 262144 65536 4
94 1000 262144 65536 4
Submit
Back to Top