問題一覧 > 通常問題

No.2136 Dice Calendar?

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 19
作問者 : kaichou243 / テスター : CuriousFairy315 srtubaki taiga0629kyopro
1 ProblemId : 8614 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-11-25 21:23:00

問題文

ストーリー

白椿さんは変わったサイコロが好きで，色々なサイコロを集めています．

今日は，サイコロカレンダーに使われそうなサイコロで遊ぶことにしました．

今，白椿さんは NN 個のサイコロを持っています． ii 番目のサイコロには出目として Si,1,…,Si,6S_{i, 1}, \ldots, S_{i, 6} が書かれています．

これらのサイコロを適当な面を上にして並び替え，一直線に並べることで作られる整数は全部で何通りあるでしょうか？

なお，白椿さんはうっかりしていたため， 66 と 99 が区別できるようなサイコロを使っています． 従って， 00 が存在しないことを除いてもサイコロカレンダーとしては使えないサイコロであることに注意してください．

サイコロカレンダーでは 66 と 99 が区別できない理由

カレンダーの場合，0101 から 3131 までの数字を二つのサイコロで作ることが求められます．

まず，0101 から 0909 まで作る必要があることから，両方のサイコロに 00 が書かれています． 同様に 1,21, 2 も 11,2211, 22 を作る必要があることから必須です．

すると残りの 66 つの面に 3,4,5,6,7,8,93,4,5,6,7,8,9 の 77 つの数字を書く必要があり，このままでは不可能です． そこで，66 をひっくり返して 99 にする，というアイデアが必要になるのです．

NN 個の 11 以上 99 以下の整数からなる多重集合が与えられます． ii 番目の多重集合は SiS_i です．

各 SiS_i から 11 要素を選び，並び替えて文字列結合することにより作られる整数が何通りあるかを  mod 998244353\bmod 998244353 で求めてください．

入力

NN
S1,1…S1,6S_{1, 1} \ldots S_{1, 6}
S2,1…S2,6S_{2, 1} \ldots S_{2, 6}
⋮\vdots
SN,1…SN,6S_{N, 1} \ldots S_{N, 6}

制約

  • 1≤N≤201 \leq N \leq 20
  • 1≤Si,j≤9 (1≤i≤N,1≤j≤6)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

まず，どちらのサイコロを前にするかで 22 通りあります．
次に，それぞれのサイコロが 66 通りあるので， 2×6×6=722 \times 6 \times 6 = 72 となります．
しかし， 11,12,13,21,22,23,31,32,3311, 12, 13, 21, 22, 23, 31, 32, 33 の 99 つはどちらのサイコロが先頭か区別できないので，99 が引かれます．
従って，答えは 72−9=6372-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

答えを 998244353998244353 で割った余りを出力することを忘れずに．

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