当前位置:首页 > 数学 > 正文
洛谷P8865种花(NOIP2022)
118+

题目大意:一个n*m的字符矩阵,其中图形C和图形F各有多少个?

题目描述

小 C 决定在他的花园里种出 $\texttt{CCF}$ 字样的图案,因此他想知道 $\texttt C$ 和 $\texttt F$ 两个字母各自有多少种种花的方案;不幸的是,花园中有一些土坑,这些位置无法种花,因此他希望你能帮助他解决这个问题。

花园可以看作有 $n\times m$ 个位置的网格图,从上到下分别为第 $1$ 到第 $n$ 行,从左到右分别为第 $1$ 列到第 $m$ 列,其中每个位置有可能是土坑,也有可能不是,可以用 $a_{i,j} = 1$ 表示第 $i$ 行第 $j$ 列这个位置有土坑,否则用 $a_{i,j} = 0$ 表示这个位置没土坑。

一种种花方案被称为 $\texttt{C-}$ **形**的,如果存在 $x_1, x_2 \in [1, n]$,以及 $y_0, y_1, y_2 \in [1, m]$,满足 $x_1 + 1 < x_2$,并且 $y_0 < y_1, y_2 \leq m$,使得第 $x_1$ **行**的第 $y_0$ 到第 $y_1$ **列**、第 $x_2$ **行**的第 $y_0$ 到第 $y_2$ **列**以及第 $y_0$ **列**的第 $x_1$ 到第 $x_2$ **行**都**不为土坑**,且只在上述这些位置上种花。

一种种花方案被称为 $\texttt{F-}$ **形**的,如果存在 $x_1, x_2, x_3 \in [1, n]$,以及 $y_0, y_1, y_2 \in [1, m]$,满足 $x_1 + 1 < x_2 < x_3$,并且 $y_0 < y_1, y_2 \leq m$,使得第 $x_1$ **行**的第 $y_0$ 到第 $y_1$ **列**、第 $x_2$ **行**的第 $y_0$ 到第 $y_2$ **列**以及第 $y_0$ **列**的第 $x_1$ 到第 $x_3$ **行**都**不为土坑**,且只在上述这些位置上种花。

样例一解释中给出了 $\texttt{C-}$ 形和 $\texttt{F-}$ 形种花方案的图案示例。

现在小 C 想知道,给定 $n, m$ 以及表示每个位置是否为土坑的值 $\{a_{i,j}\}$,$\texttt{C-}$ 形和 $\texttt{F-}$ 形种花方案分别有多少种可能?由于答案可能非常之大,你只需要输出其对 $998244353$ 取模的结果即可,具体输出结果请看输出格式部分。

输入输出格式

输入格式

第一行包含两个整数 $T, id$,分别表示数据组数和测试点编号。如果数据为样例则保证 $id = 0$。

接下来一共 $T$ 组数据,在每组数据中:

第一行包含四个整数 $n, m, c, f$,其中 $n, m$ 分别表示花园的行数、列数,对于 $c, f$ 的含义见输出格式部分。

接下来 $n$ 行,每行包含一个长度为 $m$ 且仅包含 $0$ 和 $1$ 的字符串,其中第 $i$ 个串的第 $j$ 个字符表示 $a_{i,j}$,即花园里的第 $i$ 行第 $j$ 列是不是一个土坑。

输出格式

设花园中 $\texttt{C-}$ 形和 $\texttt{F-}$ 形的种花方案分别有 $V_C$ 和 $V_F$ 种,则你需要对每一组数据输出一行用一个空格隔开的两个非负整数,分别表示 $(c \times V_C) \bmod 998244353$,$(f \times V_F ) \bmod 998244353$ ,其中 $a \bmod P$ 表示 $a$ 对 $P$ 取模后的结果。

输入输出样例

输入样例 #1

1 0
4 3 1 1
001
010
000
000

输出样例 #1

4 2

说明

**【样例 1 解释】**

四个 $\texttt{C-}$ 形种花方案为:

“`plain
**1 **1 **1 **1
*10 *10 *10 *10
**0 *** *00 *00
000 000 **0 ***
“`

其中 $\texttt*$ 表示在这个位置种花。注意 $\texttt C$ 的两横可以不一样长。

类似的,两个 $\texttt{F-}$ 形种花方案为:

“`plain
**1 **1
*10 *10
**0 ***
*00 *00
“`

**【样例 2】**

见附件下的 $\texttt{plant/plant2.in}$ 与 $\texttt{plant/plant2.ans}$。

**【样例 3】**

见附件下的 $\texttt{plant/plant3.in}$ 与 $\texttt{plant/plant3.ans}$。

**【数据范围】**

对于所有数据,保证:$1 \leq T \leq 5$,$1 \leq n, m \leq 10^3$,$0 \leq c, f \leq 1$,$a_{i,j} \in \{0, 1\}$。

| 测试点编号 | $n$ | $m$ | $c=$ | $f=$ | 特殊性质 | 测试点分值 |
| :———-: | :———-: | :———-: | :———-: | :———-: | :———-: | :———-: |
| $1$ | $\leq 1000$ | $\leq 1000$ | $0$ | $0$ | 无 | $1$ |
| $2$ | $=3$ | $=2$ | $1$ | $1$ | 无 | $2$ |
| $3$ | $=4$ | $=2$ | $1$ | $1$ | 无 | $3$ |
| $4$ | $\leq 1000$ | $=2$ | $1$ | $1$ | 无 | $4$ |
| $5$ | $\leq 1000$ | $\leq 1000$ | $1$ | $1$ | A | $4$ |
| $6$ | $\leq 1000$ | $\leq 1000$ | $1$ | $1$ | B | $6$ |
| $7$ | $\leq 10$ | $\leq 10$ | $1$ | $1$ | 无 | $10$ |
| $8$ | $\leq 20$ | $\leq 20$ | $1$ | $1$ | 无 | $6$ |
| $9$ | $\leq 30$ | $\leq 30$ | $1$ | $1$ | 无 | $6$ |
| $10$ | $\leq 50$ | $\leq 50$ | $1$ | $1$ | 无 | $8$ |
| $11$ | $\leq 100$ | $\leq 100$ | $1$ | $1$ | 无 | $10$ |
| $12$ | $\leq 200$ | $\leq 200$ | $1$ | $1$ | 无 | $6$ |
| $13$ | $\leq 300$ | $\leq 300$ | $1$ | $1$ | 无 | $6$ |
| $14$ | $\leq 500$ | $\leq 500$ | $1$ | $1$ | 无 | $8$ |
| $15$ | $\leq 1000$ | $\leq 1000$ | $1$ | $0$ | 无 | $6$ |
| $16$ | $\leq 1000$ | $\leq 1000$ | $1$ | $1$ | 无 | $14$ |

特殊性质 A:$\forall 1 \leq i \leq n, 1 \leq j \leq \left\lfloor \frac{m}{3} \right\rfloor$,$a_{i, 3 j} = 1$;

特殊性质 B:$\forall 1 \leq i \leq \left\lfloor \frac{n}{4} \right\rfloor, 1 \leq j \leq m$,$a_{4 i, j} = 1$;

解题思路

暴力做法:枚举交点,如枚举C的左上角和左下角,只要列相同,该列两点之间全是0,那么方案数就是两点右边连续0(不含自己)的数量相乘。

这就比较容易想到预处理每个位置右边连续的0数量a[i][j]、下面连续的0的数量c[i][j],判断两点之间是否全是0,只需要看c数组即可。

写着写着发现,可以从后往前计算,把预处理和计算合并到一起,利用后缀和,只需要枚举左上角的点即可,因为如果不连续,后缀和会变成零。

程序中,数组b记录图形C的后缀和,遇到1则清零。遇到零则累加——该处可以作为底部,右边有多少0就有多少种方案。

对于图形F同理,至少遇到F的第二个交点,计算方法需要用乘法原理,因为往下和往右的长度可以任意搭配。

最后,注意两个关键点中间至少隔一行,且中间必须是0。

程序实现

报歉!评论已关闭.