h995: 給電老鼠們的測驗
Tags : DP SOS 排列組合 數學
Accepted rate : 2人/2人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-06-29 20:47

Content

今天有一群電老鼠們🐭 $(\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$。

Input

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

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

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

輸出符合條件的子序列數量,$\bmod 998244353$。

Sample Input #1
1 1
1048575
Sample Output #1
1
Sample Input #2
2 2
1048574 1
Sample Output #2
1
Sample Input #3
10 5
1 2 3 4 5 6 7 8 9 10
Sample Output #3
0
Sample Input #4
10 4
314159 271828 161803 1000000 526969 548787 1 2 3 4
Sample Output #4
3
測資資訊:
記憶體限制: 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
Hint :

$100\%:無特別限制$

Tags:
DP SOS 排列組合 數學
出處:
[管理者: becaido(Caido) ]


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