No.1710 Minimum OR is X

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

No.1710 Minimum OR is X

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 70
作問者 :

chineristAC / テスター :

hitonanode 👑

Nachia

7 ProblemId : 5582 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2021-10-18 19:54:45

問題文

正整数 $N, M, K$ および非負整数 $X$ が与えられます。

長さ $N$ の非負整数列 $A = (A_{1}, A_{2}, \dots, A_{N})$ であって、以下の条件をすべて満たすものの個数を $998244353$ で割った余りを求めてください。

条件

$0 \leq A_{i} \leq 2^{M} - 1 (1 \leq i \leq N)$

$K$ 個の相異なる正整数 $1 \leq i_{1} < i_{2} < \dots < i_{K} \leq N$ を選ぶ際の $A_{i_{1}} \lor A_{i_{2}} \lor \dots \lor A_{i_{K}}$ （ $a \lor b$ で $a$ と $b$ のビットごとの論理和を表す）の最小値は $X$ である。

入力

 $N$   $M$   $K$ 
 $X$

$1 \leq N \leq 200$
$1 \leq M \leq 200$
$1 \leq K \leq N$
$0 \leq X \leq 2^{M} - 1$
$X$ は $2$ 進表記で leading zero を含めてちょうど $M$ 桁与えられる。
与えられる入力はすべて整数

出力

答えを出力してください。

最後に改行してください。

サンプル

サンプル1

入力

3 2 2
10

出力

例えば $A = (0, 2, 3)$ の場合、 $2$ つの要素を選んだときのビットごとの論理和は $A_{1} \lor A_{2} = 2$ が最小値であるため、条件を満たします。

サンプル2

入力

4 5 2
01101

出力

$X$ は leading zero を含むことがあります。

サンプル3

入力

200 40 121
1000110011111110001000100011001110011011

出力

473384304

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。

yukicoder

No.1710 Minimum OR is X

問題文

入力

出力

サンプル

サンプル1

入力

出力

サンプル2

入力

出力

サンプル3

入力

出力