题目背景
Heart beat to death.
题目描述
给定一个正整数 n。将 [0,2n) 中每个整数的二进制最低 n 位从低到高依次写在一个 2n×n 的矩阵上。矩阵两维的下标都从 0 开始。 如,当 n=3 时,矩阵是这样的:
给定 q 次询问,每次询问这个矩阵下标为 (x,y) 的格子所在的四连通块大小对 998244353 取模的值。
输入格式
第一行两个正整数 n,q。
接下来 q 行,每行两个非负整数 x,y,表示一次询问。
输出格式
输出 q 行,每行一个正整数,表示每次询问答案对 998244353 取模的值。
2 2
1 1
2 0
3
1
提示
【样例 #1 解释】
图为 n=2 时的矩阵,其中同一个颜色的为一个四连通块。
【数据范围】
本题开启捆绑测试。
SubTask |
分值 |
n≤ |
q≤ |
0 |
5 |
15 |
15 |
1 |
20 |
5×105 |
2 |
25 |
5×103 |
3 |
50 |
1018 |
5×105 |
对于 100% 的数据,0≤y<n≤1018,0≤x<min(2n,1018),1≤q≤5×105。
请选用较快的输入输出方式。