luogu#P9915. 「RiOI-03」3-2

    ID: 13882 远端评测题 1000ms 128MiB 尝试: 0 已通过: 0 难度: 4 上传者: 标签>数学洛谷原创O2优化位运算洛谷月赛Ad-hoc

「RiOI-03」3-2

题目背景

Heart beat to death.

题目描述

给定一个正整数 nn。将 [0,2n)[0,2^n) 中每个整数的二进制最低 nn从低到高依次写在一个 2n×n2^n\times n 的矩阵上。矩阵两维的下标都从 00 开始。 如,当 n=3n=3 时,矩阵是这样的:

给定 qq 次询问,每次询问这个矩阵下标为 (x,y)(x,y) 的格子所在的四连通块大小对 998244353998244353 取模的值。

输入格式

第一行两个正整数 n,qn,q

接下来 qq 行,每行两个非负整数 x,yx,y,表示一次询问。

输出格式

输出 qq 行,每行一个正整数,表示每次询问答案对 998244353998244353 取模的值。

2 2
1 1
2 0
3
1

提示

【样例 #1 解释】

图为 n=2n=2 时的矩阵,其中同一个颜色的为一个四连通块。


【数据范围】

本题开启捆绑测试。

SubTask\text{SubTask} 分值 nn\le qq\le
00 55 1515 1515
11 2020 5×1055\times 10^5
22 2525 5×1035\times 10^3
33 5050 101810^{18} 5×1055\times 10^5

对于 100%100\% 的数据,0y<n10180\le y\lt n\le 10^{18}0x<min(2n,1018)0\le x\lt \min(2^n, 10^{18})1q5×1051\le q\le 5\times 10^5

请选用较快的输入输出方式。