No.2907 Business Revealing Dora Tiles
タグ : / 解いたユーザー数 6
作問者 : 👑
amentorimaru
cleantted
👑
Nachia
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もしくは右上の雲マークをクリックしてアカウントを作成してください。