{"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/resize,m_lfit,h_200,w_265)\n\n给定 $q$ 次询问，每次询问这个矩阵下标为 $(x,y)$ 的格子所在的四连通块大小对 $998244353$ 取模的值。\n\n## Input\n\n第一行两个正整数 $n,q$。\n\n接下来 $q$ 行，每行两个非负整数 $x,y$，表示一次询问。\n\n## Output\n\n输出 $q$ 行，每行一个正整数，表示每次询问答案对 $998244353$ 取模的值。\n\n[samples]\n\n## Background\n\n> Heart beat to death[.](https://www.luogu.com.cn/problem/P9304)\n\n## Note\n\n#### 【样例 #1 解释】\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/4mglp4cn.png?x-oss-process=image/resize,m_lfit,h_200)\n\n图为 $n=2$ 时的矩阵，其中同一个颜色的为一个四连通块。\n\n***\n\n#### 【数据范围】\n\n**本题开启捆绑测试。**\n\n| $\\text{SubTask}$ | 分值 | $n\\le$ | $q\\le$ |\n| :----------: | :----------: | :----------: | :----------: |\n| $0$ | $5$ | $15$ | $15$ |\n| $1$ | $20$ | $15$ | $5\\times 10^5$ |\n| $2$ | $25$ | $5\\times 10^3$ | $5\\times 10^3$ |\n| $3$ | $50$ | $10^{18}$ | $5\\times 10^5$ |\n\n对于 $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$。\n\n**请选用较快的输入输出方式。**","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9915","tags":["数学","洛谷原创","O2优化","位运算","洛谷月赛","Ad-hoc"],"sample_group":[["2 2\n1 1\n2 0","3\n1"]],"created_at":"2026-03-03 11:09:25"}}