i235. Hehe排列組合 - 高中生程式解題系統

Content

求 $1 \text{ ~ } N$ 所組成的 $2^N$ 個子集合中，有多少個子集合的加總是 $K$ 的倍數 ($0$ 也是 $K$ 的倍數)

我們定義空集合的加總為 $0$

由於答案很大，請輸出符合條件的子集合數，$\bmod 998244353$

Input

輸入為兩個正整數 $N, K$

$1 \leq N \leq 10^{18}$

$1 \leq K \leq 150$

Output

輸出答案 $\bmod 998244353$

Sample Input #1

5 5

Sample Output #1

Sample Input #2

1 100

Sample Output #2

測資資訊：

記憶體限制： 512 MB
不公開測資點#0 (5%): 2.0s , <1K
不公開測資點#1 (5%): 2.0s , <1K
不公開測資點#2 (5%): 2.0s , <1K
不公開測資點#3 (5%): 2.0s , <1K
不公開測資點#4 (5%): 2.0s , <1K
不公開測資點#5 (5%): 2.0s , <1K
不公開測資點#6 (5%): 2.0s , <1K
不公開測資點#7 (5%): 2.0s , <1K
不公開測資點#8 (5%): 2.0s , <1K
不公開測資點#9 (5%): 2.0s , <1K
不公開測資點#10 (5%): 2.0s , <1K
不公開測資點#11 (5%): 2.0s , <1K
不公開測資點#12 (5%): 2.0s , <1K
不公開測資點#13 (5%): 2.0s , <1K
不公開測資點#14 (5%): 2.0s , <1K
不公開測資點#15 (5%): 2.0s , <1K
不公開測資點#16 (5%): 2.0s , <1K
不公開測資點#17 (5%): 2.0s , <1K
不公開測資點#18 (5%): 2.0s , <1K
不公開測資點#19 (5%): 2.0s , <1K

Hint ：

$\text{(10%) } 1 \leq N \leq 5, 1 \leq K \leq 10$

$\text{(10%) } 1 \leq N \leq 10, 1 \leq K \leq 25$

$\text{(30%) } 1 \leq N \leq 20, 1 \leq K \leq 150$

$\text{(50%) } 1 \leq N \leq 10^{18}, 1 \leq K \leq 150$

Tags:

排列組合數論

出處:

老鼠 [管理者： fire5386(Penguin07) ]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」