No.1710 Minimum OR is X
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 70
作問者 :
chineristAC
/ テスター :
hitonanode
👑 
Nachia
タグ : / 解いたユーザー数 70
作問者 :
chineristAC
/ テスター :
hitonanode
👑 Nachia
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。