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

內容

今天有一群電老鼠們🐭 $(\color{#808080}{\text{Penguin00}}$$,\ $$\color{#008000}{\text{Penguin01}}$$,\ $$\color{#03A89E}{\text{Penguin02}}$$,\ $$\color{#0000ff}{\text{Penguin03}}$$,\ $$\color{#a0a}{\text{Penguin04}}$$,\ $$\color{#ff8c00}{\text{Penguin05}}$$,\ $$\color{#ff0000}{\text{Penguin06}}$$,\ $$\text{P}\color{#ff0000}{\text{enguin07}}\color{black}{)}$ 在討論一個題目，我太弱了，但是為了能夠幫助電老鼠們，決定找一位與電老鼠們一樣電的人 (您) 來幫忙。題目如下：

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

輸入說明

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

第二行有 $n$ 個正整數 $a_i$。

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

輸出說明

輸出符合條件的子序列數量，$\bmod 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) ]

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