Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:2048 MB
Statistics

题⽬描述

观察与思考了许久,你决定再度踏上旅⾏,⾏走于洪荒⼤陆之上,你竟遇到了盘古斧的巨⼤碎⽚——太极图。对着太极图,你开始思考这漫⻓时间的所⻅所闻,在这不断的思考中,你猛地顿悟,也就是与此同时,你发现你终于回到了场上,然而你发现⽐赛只剩下正好 1 分钟了,好在凭着你开悟的⼼智,你有惊⽆险地在⽐赛只剩 59s 的时候 AK 了,接着⽆事可做的你编出了这样⼀道题:

有 $n$ 个 $k$ 维向量(也就是 $k$ 元组),第 $i$ 个向量为 $V_i$,其有⼀个值 $a_i$,其第 $j$ 维的值为 $V_{i,j}$。 定义 $\max(\overrightarrow{a},\overrightarrow{b})$ 是将两个 $k$ 维向量按位取 $\max$,具体的,若 $\overrightarrow{c}=\max(\overrightarrow{a},\overrightarrow{b})$,则 $\overrightarrow{c}$ 的第 $i$ 维的值为 $\max(a_i,b_i)$。显然,$\max$ 的定义可以拓展为对⼀个集合取 $\max$。

对于第 $i$ 维,定义两个权值函数 $f_i(x_i)=b_i^{x_i}+c_ix_i+d_i,g_i(x_i)=b_i^{x_i}+c_ix_i$ 。对于⼀个向量 $V$,定义其权值函数 $F(V)=\prod_{i=1}^{k}f_i(v_i),G(V)=\prod_{i=1}^{k}g_i(v_i)$,并且保证 $\forall i \in [1,n],G(V_i) \leq i$,你想求出下⾯这个式⼦的值: $$ \sum\limits_{S \subseteq {1,2,3,\dots,n}} \left(\left(\prod\limits_{i \in S} a_i\right) \times F(\max\limits_{i \in S}{V_i})\right) \bmod 998244353 $$

输⼊格式

第⼀⾏两个正整数 $n,k$,意义⻅题⽬描述。

第⼆⾏ $n$ 个⾮负整数,第 $i$ 个数为 $a_i$。

接下来 $n$ ⾏每⾏ $k$ 个数,第 $i$ ⾏第 $j$ 个数表⽰ $v_{i,j}$。

接下来 $k$ ⾏,每⾏三个⾮负整数表⽰ $b_i,c_i,d_i$。

输出格式

输出⼀⾏⼀个数,表⽰答案。

样例

大样例

数据范围和提⽰

对于所有数据,$1 \leq k \leq n \leq 1000,G(V_i) \leq i$。

保证 $b_1>1,b_k \leq n$,且 $\forall [2,n],b_i > b_{i-1}+1$。

保证数据没有经过特意的构造,在保证满⾜限制以外,全部通过⼀定的随机⽅式⽣成。

  • $\text{Subtask 1 (10pts)}$:$n \leq 10$

  • $\text{Subtask 2 (10pts)}$:$n \leq 20$

  • $\text{Subtask 3 (10pts)}$:$n \leq 50$

  • $\text{Subtask 4 (10pts)}$:$k \leq 5$

  • $\text{Subtask 5 (10pts)}$:$n \leq 100,k \leq 10$

  • $\text{Subtask 6 (10pts)}$:$\forall i \in [1,k],c_i=d_i=0$

  • $\text{Subtask 7 (10pts)}$:无特殊性质。