No.2136 Dice Calendar?
タグ : / 解いたユーザー数 21
作問者 :
kaichou243
/ テスター :
CuriousFairy315
srtubaki
taiga0629kyopro
Problem Statement
Story
Shirotsubaki loves unusual dice and collects all sorts of them.
Today, she decided to play with dice that look like they could be used in a dice calendar.
Shirotsubaki now has $N$ dice. The $i$-th die has $S_{i, 1}, \ldots, S_{i, 6}$ written on it as its faces.
How many different integers can be made by arranging these dice in any order in a straight line, with any face of each die facing up?
Shirotsubaki was careless, so she is using dice on which $6$ and $9$ can be distinguished. Therefore, note that these dice could not be used as a dice calendar, even setting aside the absence of $0$.
Why $6$ and $9$ cannot be distinguished in a dice calendar
A calendar requires making the numbers from $01$ to $31$ with two dice.
First, since $01$ through $09$ must be made, both dice have $0$ written on them. Similarly, $1, 2$ are also required on both dice, since $11, 22$ must be made.
This leaves the $7$ digits $3,4,5,6,7,8,9$ to be written on the remaining $6$ faces, which is impossible as it stands. Hence the idea of turning $6$ upside down to make $9$ is needed.
You are given $N$ multisets consisting of integers between $1$ and $9$, inclusive. The $i$-th multiset is $S_i$.
Find the number of integers that can be made by choosing $1$ element from each $S_i$, rearranging the chosen elements, and concatenating them as strings, $\bmod 998244353$.
Input
$N$
$S_{1, 1} \ldots S_{1, 6}$
$S_{2, 1} \ldots S_{2, 6}$
$\vdots$
$S_{N, 1} \ldots S_{N, 6}$
Constraints
- $1 \leq N \leq 20$
- $1 \leq S_{i, j} \leq 9 \ (1 \leq i \leq N, 1 \leq j \leq 6)$
- All inputs are integers.
Output
Print the answer, followed by a newline.
Sample
Sample 1
Input
2 1 2 3 4 5 6 1 2 3 7 8 9
Output
63
First, there are $2$ ways to choose which die goes in front.
Next, each die has $6$ options, giving $2 \times 6 \times 6 = 72$.
However, for the $9$ integers $11, 12, 13, 21, 22, 23, 31, 32, 33$, it cannot be distinguished which die comes first, so $9$ is subtracted.
Therefore, the answer is $72-9=63$.
Sample 2
Input
2 2 4 3 2 4 3 3 1 5 3 1 5
Output
17
A die may contain identical numbers.
Sample 3
Input
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
Output
387133740
Do not forget to print the answer modulo $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。