AtCoder Regular Contest 218
多个集合AI (CI翻译)
Problem Statement
题目描述
AI (CI翻译)You are given $N$ sequences of positive integers, each of length $M$. The $i$-th sequence is $A_i=(A_{i,1},A_{i,2},\dots,A_{i,M})$.
给定 $N$ 个正整数序列，每个序列的长度均为 $M$。第 $i$ 个序列为 $A_i=(A_{i,1},A_{i,2},\dots,A_{i,M})$。AI (CI翻译)
There are $M^N$ ways to choose one element from each of these $N$ sequences. Find the sum, modulo $998244353$, of "the number of distinct integers among the chosen elements" over all such ways.
从这 $N$ 个序列中各选取一个元素，共有 $M^N$ 种选取方式。求所有选取方式中“所选元素包含的不同整数的个数”之和，结果对 $998244353$ 取模。AI (CI翻译)
Constraints
约束条件
AI (CI翻译)$1 \le N,M \le 500$$1 \le A_{i,j} \le NM$- All input values are integers.
$1 \le N,M \le 500$$1 \le A_{i,j} \le NM$- 所有输入值均为整数。
Input
输入格式
AI (CI翻译)The input is given from Standard Input in the following format:
输入从标准输入中按以下格式给出：AI (CI翻译)
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}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
输出格式
AI (CI翻译)Output the answer.
输出答案。AI (CI翻译)
样例
Input #1
2 2
1 3
2 3
Output #1
7
For example, if $A_{1,1}$ and $A_{2,1}$ are chosen, there are two distinct integers among the chosen elements: $1$ and $2$.
The number of distinct integers is $1$ only when $A_{1,2}$ and $A_{2,2}$ are chosen, and it is $2$ in the other three cases, so the answer is $7$.
Input #2
2 2
1 1
1 2
Output #2
6
Input #3
3 5
3 1 3 4 2
5 2 1 2 3
4 6 2 5 6
Output #3
327
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。