問題一覧 > 通常問題

No.2907 Business Revealing Dora Tiles

レベル : / AI推定難易度 : 2900 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 6
作問者 : 👑 獅子座じゃない人 / テスター : 👑 amentorimaru cleantted 👑 Nachia
お気に入りにしたユーザー ProblemId : 10137 / 自分の提出
問題文最終更新日: 2024-09-26 23:01:55
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 448 (順位表) の他の問題:

Problem Statement

Rueru-kun was planning to play a business-entertainment mahjong game with his boss, but he could not gather enough players, and on top of that, he mistakenly bought as many as $10^{10^{100}}$ mahjong tiles instead of a mahjong table.

Remembering that his boss likes Kan, Rueru-kun came up with the following game.

  • Among the faces of a mahjong tile, the unique face on which a picture or characters are designed is called the "front", and the face opposite to it is called the "back".
  • Prepare $N$ sheets of grid paper with $2^{64}$ rows and $2^{64}$ columns, and call the $k$-th sheet $(1\leq k\leq N)$ "sheet $k$".
  • For sheet $k\ (1\leq k\leq N)$, the coordinates of the top-left square are $(k,(1,1))$; the coordinates of the square $1$ below the square $(k,(i,j))\ (1\leq i\leq 2^{64}-1,\ 1\leq j\leq 2^{64})$ are $(k,(i+1,j))$; and the coordinates of the square $1$ to the right of the square $(k,(i,j))\ (1\leq i\leq 2^{64},\ 1\leq j\leq 2^{64}-1)$ are $(k,(i,j+1))$.
  • For each sheet $k\ (1\leq k\leq N)$, place $1$ mahjong tile on each square $(k,(i,j))\ (1\leq i\leq H_k,\ 1\leq j\leq W_k)$. Only the tile on $(k,(H_k,W_k))$ is placed with its front facing up, and all other tiles are placed with their backs facing up.
  • The game proceeds in turns. The first player takes the first turn, and the player whose turn it is performs the following steps in order, $1$ time. When the steps are finished, the turn passes to the other player.
    • If, for all sheets $k\ (1\leq k\leq N)$, there is no tile with its front facing up on $(k,(i,j))\ (\bm{2}\leq i\leq H_k,\ \bm{2}\leq j\leq W_k)$, the player whose turn it is loses. The player who did not lose wins.
    • Otherwise, choose $1$ square $(k,(i,j))\ (1\leq k\leq N,\ \bm{2}\leq i\leq H_k,\ \bm{2}\leq j\leq W_k)$ on which a tile with its front facing up is placed.
    • Next, choose $1$ pair $(i',j')\ (1\leq i'\lt i,\ 1\leq j'\lt j)$, and flip the tiles on the squares $(k,(i,j)),(k,(i,j')),(k,(i',j)),(k,(i',j'))$. A tile that had its front facing up before flipping will have its back facing up, and a tile that had its back facing up will have its front facing up.

Rueru-kun has decided to play this game $T$ times with his boss. The first player is Rueru-kun, and the second player is the boss.

To make the entertainment more elaborate, he has decided to fix the tuple of column counts $(W_1,W_2,\ldots,W_N)$ across the $T$ games, and to use the tuple of row counts $(H_{t1},H_{t2},\ldots,H_{tN})$ in the $t$-th game $(1\leq t\leq T)$.

Find the number, modulo $998244353$, of tuples $(W_1,W_2,\ldots,W_N)$ satisfying the following conditions.

  • When both players play optimally to win, the boss, who is the second player, wins in all $T$ games.
  • For any $k\ (1\leq k\leq N)$, $\bm{2}\leq W_k\leq 2^{64}$.

Input

$N\ T$
$H_{11}\ H_{12}\ H_{13}\ \ldots\ H_{1N}$
$H_{21}\ H_{22}\ H_{23}\ \ldots\ H_{2N}$
$H_{31}\ H_{32}\ H_{33}\ \ldots\ H_{3N}$
$\vdots$
$H_{T1}\ H_{T2}\ H_{T3}\ \ldots\ H_{TN}$

  • All inputs are integers.
  • $1\leq N\leq 18$
  • $1\leq T\leq 18$
  • $2\leq H_{tk}\leq 10^{18}\ (1\leq k\leq N,\ 1\leq t\leq T)$

Output

Output the number, modulo $998244353$, of tuples $(W_1,W_2,\ldots,W_N)$ satisfying the conditions, followed by a newline.

Sample

Sample 1
Input
3 2
3 6 9
5 10 15
Output
932051909

Output the count modulo $998244353$.

An example of a tuple satisfying the conditions is $(W_1,W_2,W_3)=(12,2,2)$. Here is an example of how game $1$ proceeds in this case.

Initially, only the tiles on the squares $(1,(3,12)),\ (2,(6,2)),\ (3,(9,2))$ have their fronts facing up.

First, Rueru-kun, the first player, chooses the square $(3,(9,2))$ and the pair $(1,1)$. On sheet $3$, only the tiles on the squares $(3,(1,1)),\ (3,(1,2)),\ (3,(9,1))$ now have their fronts facing up.

Next, the boss, the second player, chooses the square $(1,(3,12))$ and the pair $(2,8)$. On sheet $1$, only the tiles on the squares $(1,(2,8)),\ (1,(2,12)),\ (1,(3,8))$ now have their fronts facing up.

Next, Rueru-kun, the first player, chooses the square $(2,(6,2))$ and the pair $(1,1)$. On sheet $2$, only the tiles on the squares $(2,(1,1)),\ (2,(1,2)),\ (2,(6,1))$ now have their fronts facing up.

Next, the boss, the second player, chooses the square $(1,(2,8))$ and the pair $(1,3)$. On sheet $1$, only the tiles on the squares $(1,(1,3)),\ (1,(1,8)),\ (1,(2,3)),\ (1,(2,12)),\ (1,(3,8))$ now have their fronts facing up.

Next, Rueru-kun, the first player, chooses the square $(1,(2,12))$ and the pair $(1,1)$. On sheet $1$, only the tiles on the squares $(1,(1,1)),\ (1,(1,3)),\ (1,(1,8)),\ (1,(1,12)),\ (1,(2,1)),\ (1,(2,3)),\ (1,(3,8))$ now have their fronts facing up.

Next, the boss, the second player, chooses the square $(1,(3,8))$ and the pair $(1,2)$. On sheet $1$, only the tiles on the squares $(1,(1,1)),\ (1,(1,2)),\ (1,(1,3)),\ (1,(1,12)),\ (1,(2,1)),\ (1,(2,3)),\ (1,(3,2))$ now have their fronts facing up.

Next, Rueru-kun, the first player, chooses the square $(1,(2,3))$ and the pair $(1,1)$. On sheet $1$, only the tiles on the squares $(1,(1,2)),\ (1,(1,12)),\ (1,(3,2))$ now have their fronts facing up.

Next, the boss, the second player, chooses the square $(1,(3,2))$ and the pair $(1,1)$. On sheet $1$, only the tiles on the squares $(1,(1,1)),\ (1,(1,12)),\ (1,(3,1))$ now have their fronts facing up.

Then, only the tiles on the squares $(1,(1,1)),\ (1,(1,12)),\ (1,(3,1)),\ (2,(1,1)),\ (2,(1,2)),\ (2,(6,1)),\ (3,(1,1)),\ (3,(1,2)),\ (3,(9,1))$ have their fronts facing up, and there is no tile with its front facing up on the squares $(k,(i,j))\ (1\leq k\leq N,\ \bm{2}\leq i\leq H_k,\ \bm{2}\leq j\leq W_k)$. Since it is the turn of Rueru-kun, the first player, in this state, the boss, the second player, wins.

Sample 2
Input
5 4
3 5 2 8 2
2 6 4 8 2
3 7 2 6 2
4 8 3 7 2
Output
0

No tuple satisfies the conditions.

Sample 3
Input
4 4
3 5 2 8
2 6 4 8
3 7 2 6
4 8 3 7
Output
498137395

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。