1442 . 字串遊戲

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

7

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

28.6% (2/7)

Tags

ioicamp ioicamp-2026

Description

這是一個關於 $n$ 顆石頭排成一列的遊戲，每顆石頭的顏色可能是黑色或白色。
遊戲由兩位玩家 Alice 和 Bob 輪流進行，由 Alice 先行。

遊戲規則如下：

  • 輪到玩家行動時，該玩家必須從石頭序列的最左邊移除長度為 $j$ 的前綴（即移除前 $j$ 顆石頭）。
  • 移除的長度 $j$ 必須滿足 $1 \le j \le k$。
  • 在被移除的 $j$ 顆石頭中，必須至少包含一顆白色石頭。
  • 若輪到某位玩家時，無法做出任何符合上述規則的合法行動，該玩家即輸掉遊戲。

現在給定整數 $n$ 與 $k$，我們假設初始盤面的每一顆石頭是獨立且隨機生成的，每顆石頭是黑色或白色的機率皆為 $\frac{1}{2}$。

請計算在隨機生成初始盤面的情況下，Alice 擁有必勝策略的機率是多少？

Input Format

輸入只有一行，此行輸入兩個整數 $n,k$。

  • $1\le n\le 10^ {12}$
  • $2\le k\le 5\times 10^ 4$

Output Format

輸出所求的機率。如果答案為最簡分數$\frac{P}{Q}$，請輸出$P \cdot Q^ {-1} \pmod{998244353}$的值。

Sample Input 1

10 2

Sample Output 1

515694593

Sample Input 2

6 3

Sample Output 2

389939201

Sample Input 3

1000000000000 50000

Sample Output 3

357276529

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資。 0
2 3~23 $nk \leq 10^ 6$ 20
3 3~32 $n \leq 10^ 6$ 20
4 33~41 $k \leq 100$ 30
5 0~52 無額外限制。 30

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 8000 524288 65536 1 5
1 8000 524288 65536 1 5
2 8000 524288 65536 1 5
3 8000 524288 65536 2 3 5
4 8000 524288 65536 2 3 5
5 8000 524288 65536 2 3 5
6 8000 524288 65536 2 3 5
7 8000 524288 65536 2 3 5
8 8000 524288 65536 2 3 5
9 8000 524288 65536 2 3 5
10 8000 524288 65536 2 3 5
11 8000 524288 65536 2 3 5
12 8000 524288 65536 2 3 5
13 8000 524288 65536 2 3 5
14 8000 524288 65536 2 3 5
15 8000 524288 65536 2 3 5
16 8000 524288 65536 2 3 5
17 8000 524288 65536 2 3 5
18 8000 524288 65536 2 3 5
19 8000 524288 65536 2 3 5
20 8000 524288 65536 2 3 5
21 8000 524288 65536 2 3 5
22 8000 524288 65536 2 3 5
23 8000 524288 65536 2 3 5
24 8000 524288 65536 3 5
25 8000 524288 65536 3 5
26 8000 524288 65536 3 5
27 8000 524288 65536 3 5
28 8000 524288 65536 3 5
29 8000 524288 65536 3 5
30 8000 524288 65536 3 5
31 8000 524288 65536 3 5
32 8000 524288 65536 3 5
33 8000 524288 65536 4 5
34 8000 524288 65536 4 5
35 8000 524288 65536 4 5
36 8000 524288 65536 4 5
37 8000 524288 65536 4 5
38 8000 524288 65536 4 5
39 8000 524288 65536 4 5
40 8000 524288 65536 4 5
41 8000 524288 65536 4 5
42 8000 524288 65536 5
43 8000 524288 65536 5
44 8000 524288 65536 5
45 8000 524288 65536 5
46 8000 524288 65536 5
47 8000 524288 65536 5
48 8000 524288 65536 5
49 8000 524288 65536 5
50 8000 524288 65536 5
51 8000 524288 65536 5
52 8000 524288 65536 5
Submit
Back to Top