h995. 給電老鼠們的測驗 - 高中生程式解題系統

內容

今天有一群電老鼠們🐭 $(Penguin00$ $,$ $Penguin01$ $,$ $Penguin02$ $,$ $Penguin03$ $,$ $Penguin04$ $,$ $Penguin05$ $,$ $Penguin06$ $,$ $P enguin07)$ 在討論一個題目，我太弱了，但是為了能夠幫助電老鼠們，決定找一位與電老鼠們一樣電的人 (您) 來幫忙。題目如下：

給你一個長度為 $n$ 的數列，請計算所有長度為 $k$ 的子序列中元素 $bitwise OR = 2^{20} - 1$ 的數量， $mod 998244353$ 。

輸入說明

第一行為兩個正整數 $n, k$ 。

第二行有 $n$ 個正整數 $a_{i}$ 。

$1 \leq k \leq n \leq 2 \times 10^{5}$
$0 \leq a_{i} \leq 2^{20} - 1$

輸出說明

輸出符合條件的子序列數量， $mod 998244353$ 。

範例輸入 #1

1 1
1048575

範例輸出 #1

範例輸入 #2

2 2
1048574 1

範例輸出 #2

範例輸入 #3

10 5
1 2 3 4 5 6 7 8 9 10

範例輸出 #3

範例輸入 #4

10 4
314159 271828 161803 1000000 526969 548787 1 2 3 4

範例輸出 #4

測資資訊：

記憶體限制： 80 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 , <1M
不公開測資點#5 (5%): 2.0s , <1M
不公開測資點#6 (5%): 2.0s , <1M
不公開測資點#7 (5%): 2.0s , <1M
不公開測資點#8 (5%): 2.0s , <10M
不公開測資點#9 (5%): 2.0s , <10M
不公開測資點#10 (5%): 2.0s , <10M
不公開測資點#11 (5%): 2.0s , <10M
不公開測資點#12 (5%): 2.0s , <10M
不公開測資點#13 (5%): 2.0s , <10M
不公開測資點#14 (5%): 2.0s , <10M
不公開測資點#15 (5%): 2.0s , <10M
不公開測資點#16 (5%): 2.0s , <10M
不公開測資點#17 (5%): 2.0s , <10M
不公開測資點#18 (5%): 2.0s , <10M
不公開測資點#19 (5%): 2.0s , <10M

提示：

$100 % ：無特別限制$

標籤:

DP SOS 排列組合數學

出處:

[管理者：

becaido (Caido) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」