No.3285 Chorus with Friends
タグ : / 解いたユーザー数 15
作問者 :
highlighter
Problem Statement
If you attack in battle with matching attack types, something called a "Kemo Chorus" is triggered, boosting various effects and making you feel happy.
So that means that when constructing a sequence, too, a sequence whose elements are all the same must be the strongest! (a leap of logic)
…I made this problem back when I had misunderstood the game's mechanics, so this is about all I have to write.
There are $N$ sequences of positive integers, each of length $M$. The $j$-th element of the $i$-th sequence is denoted by $A_{i,j}$.
There are also a sequence $F=(A_{1,1},A_{2,1},...,A_{N,1})$ and an empty sequence $X$. Starting from this state, perform the following operation in the order $i=1,2,\dots,M$.
- Choose an integer $j$ between $1$ and $N$, inclusive. Append $F_j$ to $X$, and then, if $i\neq M$, replace $F_j$ with $A_{j,i+1}$.
Find the number, modulo $998244353$, of operation sequences such that all elements of the final $X$ are equal.
Constraints
- $1\leq N,M$
- $1\leq NM \leq 300$
- $1\leq A_{i,j}\leq 300$
- All input values are integers.
Input
$N$ $M$
$A_{1,1}$ $A_{1,2}$ $\dots$ $A_{1,M}$
$A_{2,1}$ $A_{2,2}$ $\dots$ $A_{2,M}$
$\vdots$
$A_{N,1}$ $A_{N,2}$ $\dots$ $A_{N,M}$
Output
Output the answer.
Sample
Sample 1
Input
2 3 9 1 9 9 2 4
Output
1
We show the only way to make all elements of $X$ equal.
Initially, $F=(A_{1,1},A_{2,1})=(9,9),X=()$. You can obtain $X=(9,9,9)$ as follows.
- For $i=1$, choose $j=2$. $F_2=9$ is appended to $X$, and then $F_2$ is replaced with $A_{2,2}=2$, resulting in $F=(9,2),X=(9)$.
- For $i=2$, choose $j=1$. $F_1=9$ is appended to $X$, and then $F_1$ is replaced with $A_{1,3}=9$, resulting in $F=(9,2),X=(9,9)$.
- For $i=3$, choose $j=1$. $F_1=9$ is appended to $X$, resulting in $X=(9,9,9)$.
Sample 2
Input
3 3 9 9 8 2 4 4 3 5 3
Output
0
Unfortunately, these things happen sometimes.
Sample 3
Input
10 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Output
17556470
Any sequence of operations achieves the goal, which makes this the strongest case. Do not forget to find the remainder modulo $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。