「RiOI-03」3-2

Luogu

IDLGP9915

Time1000ms

Memory128MB

DifficultyP4

数学洛谷原创O2优化位运算洛谷月赛Ad-hoc

给定一个正整数 $n$。将 $[0,2^n)$ 中每个整数的二进制最低 $n$ 位**从低到高**依次写在一个 $2^n\times n$ 的矩阵上。**矩阵两维的下标都从 $0$ 开始。** 如，当 $n=3$ 时，矩阵是这样的： ![](https://cdn.luogu.com.cn/upload/image_hosting/5f6v9pru.png?x-oss-process=image/resize,m_lfit,h_200,w_265) 给定 $q$ 次询问，每次询问这个矩阵下标为 $(x,y)$ 的格子所在的四连通块大小对 $998244353$ 取模的值。 ## Input 第一行两个正整数 $n,q$。接下来 $q$ 行，每行两个非负整数 $x,y$，表示一次询问。 ## Output 输出 $q$ 行，每行一个正整数，表示每次询问答案对 $998244353$ 取模的值。 [samples] ## Background > Heart beat to death[.](https://www.luogu.com.cn/problem/P9304) ## Note #### 【样例 #1 解释】 ![](https://cdn.luogu.com.cn/upload/image_hosting/4mglp4cn.png?x-oss-process=image/resize,m_lfit,h_200) 图为 $n=2$ 时的矩阵，其中同一个颜色的为一个四连通块。 *** #### 【数据范围】 **本题开启捆绑测试。** | $\text{SubTask}$ | 分值 | $n\le$ | $q\le$ | | :----------: | :----------: | :----------: | :----------: | | $0$ | $5$ | $15$ | $15$ | | $1$ | $20$ | $15$ | $5\times 10^5$ | | $2$ | $25$ | $5\times 10^3$ | $5\times 10^3$ | | $3$ | $50$ | $10^{18}$ | $5\times 10^5$ | 对于 $100\%$ 的数据，$0\le y\lt n\le 10^{18}$，$0\le x\lt \min(2^n, 10^{18})$，$1\le q\le 5\times 10^5$。 **请选用较快的输入输出方式。**

Samples

Input #1

2 2
1 1
2 0

Output #1

3
1

API Response (JSON)

{
  "problem": {
    "name": "「RiOI-03」3-2",
    "description": {
      "content": "给定一个正整数 $n$。将 $[0,2^n)$ 中每个整数的二进制最低 $n$ 位**从低到高**依次写在一个 $2^n\\times n$ 的矩阵上。**矩阵两维的下标都从 $0$ 开始。** 如，当 $n=3$ 时，矩阵是这样的： ![](https://cdn.luogu.com.cn/upload/image_hosting/5f6v9pru.png?x-oss-process=image",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9915"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个正整数 $n$。将 $[0,2^n)$ 中每个整数的二进制最低 $n$ 位**从低到高**依次写在一个 $2^n\\times n$ 的矩阵上。**矩阵两维的下标都从 $0$ 开始。** 如，当 $n=3$ 时，矩阵是这样的：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/5f6v9pru.png?x-oss-process=image...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments