简要题意

对于三个长度为 $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 \le 3 \times 10^5$

解法

引理：设 $\text{maj}(a,b,c)$ 为 $a,b,c$ 中的众数；对于三个长度为 $n$ 的 01 字符串 $s_1,s_2,s_3$，设 $\text{maj}(s_1,s_2,s_3)$ 为长度为 $n$ 的字符串 $t$，其中 $t_i = \text{maj}(s_{1,i},s_{2,i},s_{3,i})$，则 $f(s_1,s_2,s_3) = |\{s_1,s_2,s_3,\text{maj}(s_1,s_2,s_3)\}|$。

我们首先说明以上四个字符串均满足题设条件。$s_1,s_2,s_3$ 满足条件是显然的。

对于 $t=\text{maj}(s_1,s_2,s_3)$，对于任意 $1 \le i < j \le n$，存在下标 $1 \le a < b \le 3$ 满足 $s_{a,i} = s_{b,i} = t_i$，又存在 $1 \le c < d \le 3$ 满足 $s_{c,j} = s_{d,j} = t_j$。根据抽屉原理 $\{a,b,c,d\}$ 中有两个数相等，对应的下标即是满足题设条件的 $k$。

接下来我们说明不存在其它字符串满足条件。当满足条件的字符串 $t$ 不等于 $\text{maj}(s_1,s_2,s_3)$ 时，设 $t_i \ne \text{maj}(s_1,s_2,s_3)_i$，则 $t_i$ 只在 $s_{1,i},s_{2,i},s_{3,i}$ 中出现恰好一次（不能不出现，否则不可能满足题设条件），不妨假设其为 $s_{1,i}$。此时取任意 $j \ne i$，根据题设条件必然有 $t_j = s_{1,j}$（因为 $k$ 必须取 $1$），因此 $t = s_1$。

进一步地，可以分类讨论得到 $|\{s_1,s_2,s_3,\text{maj}(s_1,s_2,s_3)\}| = 4 - \sum_{i=1}^3 [\text{maj}(s_1,s_2,s_3) = s_i]$：

• $f(s_1,s_2,s_3) = 4$ 时四个字符串两两不同；
• $f(s_1,s_2,s_3) = 3$ 时必然是某个 $s_i = \text{maj}(s_1,s_2,s_3)$ 的情况而不是 $s_i = s_j$ 的情况，因为 $s_i = s_j$ 会直接导致 $\text{maj}(s_1,s_2,s_3) = s_i$；
• $f(s_1,s_2,s_3) = 2$ 时必然是 $s_i = s_j = \text{maj}(s_1,s_2,s_3)$ 且剩余的字符串跟它们不同的情况；
• $f(s_1,s_2,s_3) = 1$ 时必然是四个字符串相等的情况。

由于期望的线性性，只需要计算 $\Pr[\text{maj}(s_1,s_2,s_3) = s_i]$ 即可。由于每一位的随机事件是独立的，所以直接把每一位相等的概率乘起来就行了。

复杂度 $O(n)$。