問題一覧 > 通常問題

No.1710 Minimum OR is X

レベル : / AI推定難易度 : 2000 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 73
作問者 : chineristAC / テスター : 👑 hitonanode 👑 Nachia
お気に入りにしたユーザー ProblemId : 5582 / 自分の提出
問題文最終更新日: 2021-10-18 19:54:45
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 318 (順位表) の他の問題:

Problem Statement

You are given positive integers $N,\ M,\ K$ and a non-negative integer $X$.

Find the number, modulo $998244353$, of sequences of non-negative integers $A=(A_1,\ A_2,\ \dots,\ A_N)$ of length $N$ that satisfy all of the following conditions.

Conditions

  • $0 \le A_i \le 2^{M}-1\ (1\le i \le N)$

  • The minimum value of $A_{i_1}\lor A_{i_2} \lor \dots \lor A_{i_K}$ (where $a\lor b$ denotes the bitwise OR of $a$ and $b$) over all choices of $K$ distinct positive integers $1 \le i_1 < i_2 < \dots < i_K \le N$ is $X$.

Input

$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$ is given in base $2$ with exactly $M$ digits, including leading zeros.
  • All values in the input are integers.

Output

Print the answer.

End the output with a newline.

Sample

Sample 1
Input
3 2 2
10
Output
16

For example, when $A=(0,\ 2,\ 3)$, the minimum bitwise OR when choosing $2$ elements is $A_1 \lor A_2=2$, so the conditions are satisfied.

Sample 2
Input
4 5 2
01101
Output
66725

$X$ may contain leading zeros.

Sample 3
Input
200 40 121
1000110011111110001000100011001110011011
Output
473384304

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