#P10497. [2021年联测]很大

    ID: 9614 传统题 2000ms 512MiB 尝试: 2 已通过: 2 难度: 7 上传者: 标签>CF2300数学数论组合数学模运算DFS矩阵数据结构

[2021年联测]很大

题目描述

一个矩阵的元素两两不同,有 n=2an=2^a 行、m=2bm=2^b 列,按行连续存放在内存中。原矩阵第 ii 行第 jj 列的元素放在内存第 m(i−1)+jm(i-1)+j 个位置,下标从 11 开始。

要在原内存中完成矩阵转置,应把该元素移到第 n(j−1)+in(j-1)+i 个位置。一次操作可以交换任意两个内存位置的元素。求完成转置至少需要多少次交换。

输入格式

输入包含若干行,读到文件末尾为止。每行两个整数 a,ba,b,表示一次询问。

输出格式

对每次询问输出一行一个整数,表示所需最少交换次数对 998244353998244353 取模的结果。

样例

1 1
1 2
762395 50914
1
4
994178060

2×22\times2 的矩阵只需交换第 (1,2)(1,2) 和第 (2,1)(2,1) 个元素的位置。2×42\times4 的矩阵需要四次交换。

数据范围

a,ba,b 为非负整数,0≤a+b≤1060\le a+b\le10^6,询问次数不超过 10510^5。时间限制 22 秒,空间限制 512512 MB。

子任务 分值 额外限制 询问次数上界
1 3 a=0a=0 或 b=0b=0 10510^5
2 20 a+b≤20a+b\le20 240
3 17 10510^5
4 30 a+b≤106a+b\le10^6 1
5 10510^5

原 PDF 题面