No.2907 Business Revealing Dora Tiles
タグ : / 解いたユーザー数 6
作問者 : 👑
amentorimaru
cleantted
👑 
Nachia
問題文
ルエルくんは、上司と接待麻雀をするつもりでしたが、同卓者を集められなかったうえに麻雀卓と間違えて $10^{10^{100}}$ 個もの麻雀牌を購入してしまいました。
上司がカンを好きであることを思い出したルエルくんは、以下のようなゲームを考えました。
- 麻雀牌の面のうち、絵や文字がデザインされている唯一の面を「表面」、その背面を「裏面」と呼ぶことにする。
- $2^{64}$ 行 $2^{64}$ 列の方眼紙を $N$ 枚用意し、 $k$ 枚目の方眼紙 $(1\leq k\leq N)$ を「方眼紙 $k$ 」と呼ぶことにする。
- 方眼紙 $k\ (1\leq k\leq N)$ の最も左上のマスの座標を $(k,(1,1))$ とし、マス $(k,(i,j))\ (1\leq i\leq 2^{64}-1,\ 1\leq j\leq 2^{64})$ の $1$ つ下のマスの座標を $(k,(i+1,j))$ 、マス $(k,(i,j))\ (1\leq i\leq 2^{64},\ 1\leq j\leq 2^{64}-1)$ の $1$ つ右のマスの座標を $(k,(i,j+1))$ とする。
- それぞれの方眼紙 $k\ (1\leq k\leq N)$ について、マス $(k,(i,j))\ (1\leq i\leq H_k,\ 1\leq j\leq W_k)$ 上に $1$ つずつ麻雀牌を置く。 $(k,(H_k,W_k))$ 上の麻雀牌のみ表面を上にし、その他の麻雀牌は裏面を上にする。
- ゲームの進行は手番制である。最初に先手に手番が回り、手番が回ってきたプレイヤーは以下の操作を順に $1$ 回行う。操作が終了すると手番はもう片方のプレイヤーに回る。
- 全ての方眼紙 $k\ (1\leq k\leq N)$ について、表面を上にした麻雀牌が $(k,(i,j))\ (\bm{2}\leq i\leq H_k,\ \bm{2}\leq j\leq W_k)$ 上にない場合、手番の回ってきたプレイヤーが負けである。負けなかったほうのプレイヤーが勝ちとなる。
- そうでない場合、表面を上にした麻雀牌が置かれているマス $(k,(i,j))\ (1\leq k\leq N,\ \bm{2}\leq i\leq H_k,\ \bm{2}\leq j\leq W_k)$ を $1$ つ選ぶ。
- 次に、組 $(i',j')\ (1\leq i'\lt i,\ 1\leq j'\lt j)$ を $1$ つ選び、マス $(k,(i,j)),(k,(i,j')),(k,(i',j)),(k,(i',j'))$ にある麻雀牌をめくる。めくる前に表面が上であれば裏面が上になり、裏面が上であれば表面が上になる。
ルエルくんは、上司と $T$ 回このゲームをプレイすることにしました。先手がルエルくん、後手が上司です。
凝った接待をするために、 $T$ 回のゲームで列数の組 $(W_1,W_2,\ldots,W_N)$ は固定し、 $t$ 回目 $(1\leq t\leq T)$ のゲームでは行数の組を $(H_{t1},H_{t2},\ldots,H_{tN})$ にすることにしました。
以下の条件を満たす組 $(W_1,W_2,\ldots,W_N)$ の個数を $998244353$ で割った余りを求めてください。
- 両者が勝ちを目指して最適な操作を行うとき、 $T$ 回全てのゲームで、後手の上司が勝つ。
- 任意の $k\ (1\leq k\leq N)$ について、 $\bm{2}\leq W_k\leq 2^{64}$ である。
入力
$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}$
- 入力は全て整数
- $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)$
出力
条件を満たす組 $(W_1,W_2,\ldots,W_N)$ の個数を $998244353$ で割った余りを出力し、最後に改行してください。
サンプル
サンプル1
入力
3 2 3 6 9 5 10 15
出力
932051909
個数を $998244353$ で割った余りを出力してください。
条件を満たす組の例として、 $(W_1,W_2,W_3)=(12,2,2)$ があります。この場合の $1$ 回目のゲームの進行例を示します。
はじめ、マス $(1,(3,12)),\ (2,(6,2)),\ (3,(9,2))$ に置かれた麻雀牌のみ表面が上になっています。
まず、先手のルエルくんがマス $(3,(9,2))$ と組 $(1,1)$ を選びます。方眼紙 $3$ について、マス $(3,(1,1)),\ (3,(1,2)),\ (3,(9,1))$ に置かれた麻雀牌のみ表面が上になります。
次に、後手の上司がマス $(1,(3,12))$ と組 $(2,8)$ を選びます。方眼紙 $1$ について、マス $(1,(2,8)),\ (1,(2,12)),\ (1,(3,8))$ に置かれた麻雀牌のみ表面が上になります。
次に、先手のルエルくんがマス $(2,(6,2))$ と組 $(1,1)$ を選びます。方眼紙 $2$ について、マス $(2,(1,1)),\ (2,(1,2)),\ (2,(6,1))$ に置かれた麻雀牌のみ表面が上になります。
次に、後手の上司がマス $(1,(2,8))$ と組 $(1,3)$ を選びます。方眼紙 $1$ について、マス $(1,(1,3)),\ (1,(1,8)),\ (1,(2,3)),\ (1,(2,12)),\ (1,(3,8))$ に置かれた麻雀牌のみ表面が上になります。
次に、先手のルエルくんがマス $(1,(2,12))$ と組 $(1,1)$ を選びます。方眼紙 $1$ について、マス $(1,(1,1)),\ (1,(1,3)),\ (1,(1,8)),\ (1,(1,12)),\ (1,(2,1)),\ (1,(2,3)),\ (1,(3,8))$ に置かれた麻雀牌のみ表面が上になります。
次に、後手の上司がマス $(1,(3,8))$ と組 $(1,2)$ を選びます。方眼紙 $1$ について、マス $(1,(1,1)),\ (1,(1,2)),\ (1,(1,3)),\ (1,(1,12)),\ (1,(2,1)),\ (1,(2,3)),\ (1,(3,2))$ に置かれた麻雀牌のみ表面が上になります。
次に、先手のルエルくんがマス $(1,(2,3))$ と組 $(1,1)$ を選びます。方眼紙 $1$ について、マス $(1,(1,2)),\ (1,(1,12)),\ (1,(3,2))$ に置かれた麻雀牌のみ表面が上になります。
次に、後手の上司がマス $(1,(3,2))$ と組 $(1,1)$ を選びます。方眼紙 $1$ について、マス $(1,(1,1)),\ (1,(1,12)),\ (1,(3,1))$ に置かれた麻雀牌のみ表面が上になります。
すると、マス $(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))$ に置かれた麻雀牌のみ表面が上になり、マス $(k,(i,j))\ (1\leq k\leq N,\ \bm{2}\leq i\leq H_k,\ \bm{2}\leq j\leq W_k)$ 上には表面を上にした麻雀牌はありません。この状態で先手のルエルくんに手番が回ってくるため、後手の上司の勝ちとなります。
サンプル2
入力
5 4 3 5 2 8 2 2 6 4 8 2 3 7 2 6 2 4 8 3 7 2
出力
0
条件を満たす組は存在しません。
サンプル3
入力
4 4 3 5 2 8 2 6 4 8 3 7 2 6 4 8 3 7
出力
498137395
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。