No.2136 Dice Calendar?
タグ : / 解いたユーザー数 19
作問者 :
kaichou243
/ テスター :
CuriousFairy315
srtubaki
taiga0629kyopro
問題文
ストーリー
白椿さんは変わったサイコロが好きで，色々なサイコロを集めています．
今日は，サイコロカレンダーに使われそうなサイコロで遊ぶことにしました．
今，白椿さんは $N$ 個のサイコロを持っています． $i$ 番目のサイコロには出目として $S_{i, 1}, \ldots, S_{i, 6}$ が書かれています．
これらのサイコロを適当な面を上にして並び替え，一直線に並べることで作られる整数は全部で何通りあるでしょうか？
なお，白椿さんはうっかりしていたため， $6$ と $9$ が区別できるようなサイコロを使っています． 従って， $0$ が存在しないことを除いてもサイコロカレンダーとしては使えないサイコロであることに注意してください．
サイコロカレンダーでは $6$ と $9$ が区別できない理由
カレンダーの場合，$01$ から $31$ までの数字を二つのサイコロで作ることが求められます．
まず，$01$ から $09$ まで作る必要があることから，両方のサイコロに $0$ が書かれています． 同様に $1, 2$ も $11, 22$ を作る必要があることから必須です．
すると残りの $6$ つの面に $3,4,5,6,7,8,9$ の $7$ つの数字を書く必要があり，このままでは不可能です． そこで，$6$ をひっくり返して $9$ にする，というアイデアが必要になるのです．
$N$ 個の $1$ 以上 $9$ 以下の整数からなる多重集合が与えられます． $i$ 番目の多重集合は $S_i$ です．
各 $S_i$ から $1$ 要素を選び，並び替えて文字列結合することにより作られる整数が何通りあるかを $\bmod 998244353$ で求めてください．
入力
$N$
$S_{1, 1} \ldots S_{1, 6}$
$S_{2, 1} \ldots S_{2, 6}$
$\vdots$
$S_{N, 1} \ldots S_{N, 6}$
制約
- $1 \leq N \leq 20$
- $1 \leq S_{i, j} \leq 9 \ (1 \leq i \leq N, 1 \leq j \leq 6)$
- 入力は全て整数
出力
答えを出力し，最後に改行してください．
サンプル
サンプル1
入力
2 1 2 3 4 5 6 1 2 3 7 8 9
出力
63
まず，どちらのサイコロを前にするかで $2$ 通りあります．
次に，それぞれのサイコロが $6$ 通りあるので， $2 \times 6 \times 6 = 72$ となります．
しかし， $11, 12, 13, 21, 22, 23, 31, 32, 33$ の $9$ つはどちらのサイコロが先頭か区別できないので，$9$ が引かれます．
従って，答えは $72-9=63$ 通りとなります．
サンプル2
入力
2 2 4 3 2 4 3 3 1 5 3 1 5
出力
17
同じ数字が含まれている場合もあります．
サンプル3
入力
9 1 2 3 4 5 6 2 3 4 5 6 7 3 4 5 6 7 8 4 5 6 7 8 9 1 5 6 7 8 9 1 2 6 7 8 9 1 2 3 7 8 9 1 2 3 4 8 9 1 2 3 4 5 9
出力
387133740
答えを $998244353$ で割った余りを出力することを忘れずに．
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。