問題一覧 > 通常問題

No.3285 Chorus with Friends

レベル : / AI推定難易度 : 2000 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 15
作問者 : hirayuu_yc / テスター : highlighter
お気に入りにしたユーザー ProblemId : 12182 / 自分の提出
問題文最終更新日: 2025-09-24 13:20:29
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 484 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。