No.3285 Chorus with Friends
レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 12
作問者 :
hirayuu_yc
/ テスター :
highlighter
タグ : / 解いたユーザー数 12
作問者 :
hirayuu_yc
/ テスター :
highlighter
問題文最終更新日: 2025-09-24 13:20:29
問題文
バトルのときに攻撃のタイプを揃えて攻撃すると「けもコーラス」なるものが発動し、いろいろ効果が上がって嬉しい気持ちになります。
ってことは、数列を構築するときも全ての要素が同じ数列なら最強に決まってますね！（論理の飛躍）
…この問題、仕様を勘違いしていたときに作ったのでこれくらいしか書くことがないんですよね
長さ $M$ の正整数列が $N$ 個あります。$i$ 番目の数列の $j$ 番目の要素を $A_{i,j}$ と表記します。
また、数列 $F=(A_{1,1},A_{2,1},...,A_{N,1})$ と空の数列 $X$ があります。ここから、$i=1,2,\dots,M$ の順に以下の操作を行います。
- $1$ 以上 $N$ 以下の整数 $j$ を選ぶ。$X$ に $F_j$ を追加して、$i\neq M$ ならば $F_j$ を $A_{j,i+1}$ に置き換える。
最終的な $X$ の要素がすべて等しいような操作列の個数を $998244353$ で割ったあまりを求めてください。
制約
- $1\leq N,M$
- $1\leq NM \leq 300$
- $1\leq A_{i,j}\leq 300$
- 入力はすべて整数
入力
$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}$
出力
答えを出力せよ。
サンプル
サンプル1
入力
2 3 9 1 9 9 2 4
出力
1
$X$ の要素をすべて等しくする唯一の方法を示します。
はじめ、$F=(A_{1,1},A_{2,1})=(9,9),X=()$ です。以下のようにすることで $X=(9,9,9)$ とすることができます。
- $i=1$ のとき、$j=2$ を選ぶ。$X$ に $F_2=9$ が追加されたのち $F_2$ が $A_{2,2}=2$ に置き換わり、$F=(9,2),X=(9)$ となる。
- $i=2$ のとき、$j=1$ を選ぶ。$X$ に $F_1=9$ が追加されたのち $F_1$ が $A_{1,3}=9$ に置き換わり、$F=(9,2),X=(9,9)$ となる。
- $i=3$ のとき、$j=1$ を選ぶ。$X$ に $F_1=9$ が追加され、$X=(9,9,9)$ となる。
サンプル2
入力
3 3 9 9 8 2 4 4 3 5 3
出力
0
残念ですが、そういうこともあります。
サンプル3
入力
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
出力
17556470
どのように操作をしても目的を達成できて最強ですね。$998244353$ で割ったあまりを求めることを忘れないでください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。