h995. 給電老鼠們的測驗
標籤 : DP SOS 排列組合 數學
通過比率 : 3人/4人 ( 75% ) [非即時]
評分方式:
Tolerant

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

內容

今天有一群電老鼠們🐭 $(\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
1
範例輸入 #2
2 2
1048574 1
範例輸出 #2
1
範例輸入 #3
10 5
1 2 3 4 5 6 7 8 9 10
範例輸出 #3
0
範例輸入 #4
10 4
314159 271828 161803 1000000 526969 548787 1 2 3 4
範例輸出 #4
3
測資資訊:
記憶體限制: 80 MB
提示 :

$100\%:無特別限制$

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

本題狀況 本題討論 排行

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