問題一覧 > 通常問題

No.1710 Minimum OR is X

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 71
作問者 : chineristACchineristAC / テスター : 👑 NachiaNachia 👑 hitonanodehitonanode
7 ProblemId : 5582 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-10-18 19:54:45

問題文

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

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

条件

  • $0 \le A_i \le 2^{M}-1\ (1\le i \le N)$
  • $K$ 個の相異なる正整数 $1 \le i_1 < i_2 < \dots < i_K \le 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 \le N \le 200$
  • $1 \le M \le 200$
  • $1 \le K \le N$
  • $0 \le X \le 2^M-1$
  • $X$ は $2$ 進表記で leading zero を含めてちょうど $M$ 桁与えられる。
  • 与えられる入力はすべて整数

出力

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

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

サンプル

サンプル1
入力
3 2 2
10
出力
16

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

サンプル2
入力
4 5 2
01101
出力
66725

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

サンプル3
入力
200 40 121
1000110011111110001000100011001110011011
出力
473384304

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