草长莺飞二月天

题目

杂草多了，庄稼就不长了。

学校又开始了新一学年的开心农场活动，小J和小R今年也参与了进来。

他们走到开心农场后，发现整个农场被分成了 N 行 M 列，由于太久没有种植农作物，每个格子上都长上了高度为 w_i,j 的杂草。

现在每个学院分配了一行的土地来进行今年的播种，每个学院都拿到了不同的农作物，对于第 i 行的学院，他们所拿到的农作物的生命力为 a_i，只有当农作物的生命力大于杂草的时候，这一个格子上的农作物才能够存活下来，因此为了不浪费种子，当我们已知农作物不能在这一块土地上存活时我们便不会播种。

另外，由于农作物之间会互相争夺养分，为了保障农作物能够茁壮成长，我们不会在任意相邻的两个格子上同时种植农作物。

现在，每个学院的同学将同时开始播种，小J和小R想知道对于整个农场而言一共会有多少种不同的播种方案，请注意完全不播种也是一种方案，由于方案数可能会较大请取模 998244353 输出。

输入：第一行两个数 N, M；接下来一行，N 个整数，依次表达每个学院农作物的生命力 a_i；接下来 N 行，每行 M 个整数，依次表达每个格子上杂草的高度 w_i,j。
输出：一行一个整数，表示符合条件的总方案数。

样例1：

3 3
1 2 3
2 2 2
2 2 2
2 2 2

5

样例2：

3 3
1 2 3
0 0 0
1 1 1
2 2 2

63

提示：对于 30% 的数据，保证 1≤N,M≤3。对于 60% 的数据，保证 1≤N,M≤5，N×M≤15。对于 100% 的数据，保证 1≤N,M≤13，w_i,j,a_i≤10⁵。

思路

复杂度分析

• 时间复杂度：
• 空间复杂度：

← 返回菜鸟的coding