問題一覧 > 通常問題

No.1403 調和の魔法陣

レベル : / 実行時間制限 : 1ケース 3.153秒 / メモリ制限 : 315 MB / 通常問題
タグ : / 解いたユーザー数 3
作問者 : CuriousFairy315CuriousFairy315 / テスター : 37zigen37zigen
1 ProblemId : 4596 / 出題時の順位表
問題文最終更新日: 2021-02-18 13:50:39

問題文

315さんは魔法陣の勉強をしています。
魔法陣には五芒星や六芒星、円陣など様々な形のものがあり、そこに適切な強さの触媒を置くことで効果を発揮します。
今回書く魔法陣は長方形を縦に $H$ 個、横に $W$ 個に分割し、その各マスに触媒を置くことで効果を発揮するものです。
しかし、魔法陣は調和を保っていないと魔力の伝播にムラが発生し、最終的に術式が破綻してしまいます。
今回書く魔法陣が調和を保っている状態とは、どのマスについてもそのマスを中心とする $3 \times 3$ マスの範囲の触媒の強さの合計$S$が等しいことを言います。
すなわち、 $M_{y, x}$ をマス $(x, y)$ の触媒の強さとすると、 $1 \leq x \leq W, 1 \leq y \leq H$ を満たす整数 $x, y$ 全てに対し $\sum_{i=y-1}^{y+1} \sum_{j=x-1}^{x+1} M_{i, j} = S$ である必要があります。
またこの時、魔法陣の強さは $S$ となります。
315さんは強さが $1$ 以上 $9$ 以下の触媒をたくさん持っているので、この触媒を適切に配置することで強さ $X$ の調和を保っている魔法陣を作りたいです。
触媒は1マスに高々1個まで配置できる(配置しないこともできる)ので、 $1 \leq x \leq W, 1 \leq y \leq H$ を満たす整数 $x, y$ 全てに対し $0 \leq M_{y, x} \leq 9$ であり、それ以外の $x, y$ に対し $M_{y, x} = 0$ となります。
魔法陣に触媒を置く方法は全部で $10^{WH}$ 通りもありますが、その中で調和を保っている魔法陣の置き方はどのようなものがあるでしょうか?
テストケースは全部で $T$ ケース与えられます。
各テストケースでは $W_i, H_i, X_i$ が与えられるので、強さ $X_i$ の調和を保っている魔法陣が何通りあるか求めてください。
ただし答えは非常に大きくなる可能性があるので、答えを $998244353$ (素数)で割った余りを出力してください。

入力

$T$
$W_1\ H_1\ X_1$
$\vdots$
$W_T\ H_T\ X_T$

  • $1 \leq T \leq 10000$
  • $1 \leq W_i, H_i \leq 600$
  • $0 \leq X_i \leq 81$
  • 入力は全て整数である

出力

第 $i$ 行目には、大きさが縦に $H_i$ 、横に $W_i$ で強さが $X_i$ の調和を保っている魔法陣が何通り作れるかを求め、答えを $998244353(= 119 \times 2^{23} + 1)$ で割った余りを出力してください。
最後に改行してください。

サンプル

サンプル1
入力
1
2 2 6
出力
84

答えは $_{4}H_{6}=_{4+6-1}C_{6}=84$ 通りになります。

サンプル2
入力
1
5 2 4
出力
259

サンプル3
入力
1
3 3 81
出力
0

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