問題一覧 > 通常問題

No.2711 Connecting Lights

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 120
作問者 : 👑 Nafmo2Nafmo2 / テスター : dyktr_06dyktr_06 sepa38sepa38 ryota2357ryota2357
0 ProblemId : 9988 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-03-27 15:52:38

問題文

縦 $N$ 行,横 $M$ 列 のグリッドがあり,それぞれのマスに オン/オフ を自由に切り替えられる電球があります.
ここで,上から $i$ 番目,左から $j$ 番目の電球について

  • 電球がオンのとき:$A_{i,j} = 1$
  • 電球がオフのとき:$A_{i,j} = 0$
と表記する.$1 \leq j \leq M-1$を満たす全ての列 $j$ について,列 $j$ と 列 $j+1$ のどちらも電球がオンになっている行の数が $K$ 個以上となる電球のつけ方の場合の数を $998244353$ で割ったあまりを求めてください.

より厳密には,以下の条件を満たす電球のつけ方の場合の数を $998244353$ で割ったあまりを出力してください.

  • $1 \leq j \leq M-1$ を満たす全ての $j$ について,以下の条件を満たす
    • $A_{i,j} = 1$ かつ $A_{i,j+1} = 1$ となる $i$ が $K$ 個以上存在する

入力

$N\ M \ K$

  • $1 \leq K \leq N \leq 5$
  • $1 \leq M \leq 2 \times 10^4$
  • 入力はすべて整数

出力

条件を満たす電球のつけ方の場合の数を $998244353$ で割ったあまりを出力してください.最後に改行してください.

サンプル

サンプル1
入力
2 2 1
出力
7

以下の $7$ 通りが全てです.

サンプル2
入力
3 4 1
出力
1129

サンプル3
入力
5 10 3
出力
252507990

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