P5300 [GXOI/GZOI2019]与或和

    • 278通过
    • 570提交
  • 题目提供者 StudyingFather
  • 评测方式 云端评测
  • 标签 各省省选 2019
  • 难度 省选/NOI-
  • 时空限制 2000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Freda 学习了位运算和矩阵以后,决定对这种简洁而优美的运算,以及蕴含深邃空间的结构进行更加深入的研究。

    对于一个由非负整数构成的矩阵,她定义矩阵的 $\texttt{AND}$ 值为矩阵中所有数二进制 $\texttt{AND(\&)}$ 的运算结果;定义矩阵的 $\texttt{OR}$ 值为矩阵中所有数二进制 $\texttt{OR(|)}$ 的运算结果。

    给定一个 $N \times N$ 的矩阵,她希望求出:

    1. 该矩阵的所有子矩阵的 $\texttt{AND}$ 值之和(所有子矩阵 $\texttt{AND}$ 值相加的结果)。
    2. 该矩阵的所有子矩阵的 $\texttt{OR}$ 值之和(所有子矩阵 $\texttt{OR}$ 值相加的结果)。

    接下来的剧情你应该已经猜到——Freda 并不想花费时间解决如此简单的问题,所以这个问题就交给你了。

    由于答案可能非常的大,你只需要输出答案对 $1,000,000,007 (10^9 + 7)$ 取模后的结果。

    输入输出格式

    输入格式:

    输入文件的第一行是一个正整数 $N$,表示矩阵的尺寸。

    接下来 $N$ 行,每行 $N$ 个自然数,代表矩阵的一行。相邻两个自然数之间由一个或多个空格隔开。

    输出格式:

    输出只有一行,包含两个用空格隔开的整数,第一个应为所有子矩阵 $\texttt{AND}$ 值之和除以 $10^9 + 7$ 的余数,第二个应为所有子矩阵 $\texttt{OR}$ 值之和除以 $10^9 + 7$ 的余数。

    输入输出样例

    输入样例#1: 复制
    3
    1 0 0
    0 0 0
    0 0 0
    输出样例#1: 复制
    1 9
    输入样例#2: 复制
    3
    1 2 3
    4 5 6
    7 8 9
    输出样例#2: 复制
    73 314

    说明

    样例1解释

    该 $3 \times 3$ 矩阵共有 $9$ 个 $1 \times 1$ 子矩阵、$6$ 个 $1 \times 2$ 子矩阵、$6$ 个 $2 \times 1$ 子矩阵、$4$ 个 $2 \times 2$ 子矩阵、3 个 $1 \times 3$ 子矩阵、$3$ 个 $3 \times 1$ 子矩阵、$2$ 个 $2 \times 3$ 子矩阵、$2$ 个 $3 \times 2$ 子矩阵和 $1$ 个 $3 \times 3$ 子矩阵。
    只有一个子矩阵(仅由第一行第一列的那个元素构成的 $1 \times 1$ 矩阵)$\texttt{AND}$ 值为 $1$,其余子矩阵的 $\texttt{AND}$ 值均为 $0$,总和为 $1$。
    包含第一行第一列那个元素的子矩阵有 $9$ 个,它们的 $\texttt{OR}$ 值为 $1$,其余子矩阵的 $\texttt{OR}$ 值为 $0$,总和为 $9$。

    数据范围

    测试点编号 $n$ 的规模 矩阵中的自然数
    $1$ $1 \le n \le 10$ $\le 100$
    $2$ $1 \le n \le 10$ $\le 100$
    $3$ $1 \le n \le 100$ $\le 100$
    $4$ $1 \le n \le 100$ $\le 100$
    $5$ $1 \le n \le 100$ $\le 100$
    $6$ $1 \le n \le 1,000$ $\le 2^{31} - 1$
    $7$ $1 \le n \le 1,000$ $\le 2^{31} - 1$
    $8$ $1 \le n \le 1,000$ $\le 2^{31} - 1$
    $9$ $1 \le n \le 1,000$ $\le 2^{31} - 1$
    $10$ $1 \le n \le 1,000$ $\le 2^{31} - 1$
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。