4284. [THUPC 2025 Final] 好串

【题目描述】

对于三个长度为 $n$ 的 01 字符串 $s_1,s_2,s_3$，称长度为 $n$ 的 01 字符串 $t$ 是好的当且仅当 $\forall 1 \le i,j \le n, \exists k \in \{1,2,3\}, s_{k,i} = t_i, s_{k,j} = t_j$。设 $f(s_1,s_2,s_3)$ 为这样的好的串的数量。

现在我们有三个长度为 $n$ 的随机 01 字符串 $s_1,s_2,s_3$，其中 $s_i (1 \le i \le 3)$ 的第 $j (1 \le j \le n)$ 个字符有 $\frac{p_{i,j}}{9}$ 的概率为 1，$\left(1 - \frac{p_{i,j}}{9}\right)$ 的概率为 0，其中 $p_{i,j}$ 是一个 $0$ 至 $9$ 的整数。所有的随机事件是独立的。你需要求 $f(s_1,s_2,s_3)$ 的期望，对 $998244353$ 取模。

【输入格式】

输入第一行一个整数 $n\ (3 \le n \le 3 \times 10^5)$ 表示字符串长度，接下来一个 $3$ 行 $n$ 列的数字矩阵，其中第 $i$ 行第 $j$ 列的字符表示 $p_{i,j}$。

【输出格式】

输出一个整数表示答案对 $998244353$ 取模的值。

【输入样例 1】

3
900
090
009

【输出样例 1】

4

【样例解释 1】

在该组样例中，$s_1, s_2, s_3$ 分别为 100, 010, 001，四种方案分别为 100、010、001、000。

【输入样例 2】

3
999
999
999

【输出样例 2】

1

【输入样例 3】

10
0123456789
1234567890
2345678901

【输出样例 3】

612360617

【来源】

清华大学学生算法协会 GitLink 仓库