i235: Hehe排列組合
Tags : 排列組合 數論
Accepted rate : 2人/3人 ( 67% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-07-12 00:00

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
8
Sample Input #2
1 100
Sample Output #2
1
測資資訊:
記憶體限制: 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
沒有發現任何「解題報告」