問題一覧 > 通常問題

No.1531 く2

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 21
作問者 : PCTprobabilityPCTprobability / テスター : tatyamtatyam ngtkanangtkana
9 ProblemId : 6444 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-06-04 15:55:50

問題文

右下に無限に広がる $2$ 次元グリッドがあります。

上から $i$ 番目、左から $j$ 番目のマスを $(i,j)$ と呼びます。

全てのマスには $1$ 個非負整数が書き込まれています。$(i,j)$ には $A_{i,j}$ が書かれています。

始め、$K\ \mathrm{and}\ i=i$ を満たす非負整数 $i$ に対して $A_{0,i}=1$ となっています。それ以外のマスについては $A_{p,q}=0$ となっています。

以下の操作を $N$ 回行います。

  • 全てのマスに対して同時に書かれている整数を左と上とのマスとの $\mathrm{xor}$ に置き換える。厳密には、全てのマス $(i,j)$ に対して同時に $A_{i,j}$ を $A_{i,j}\ \mathrm{xor}\ A_{i-1,j}\ \mathrm{xor}\ A_{i,j-1}$ に置き換える。ただし、$A_{-1,i}=A_{i,-1}=0$ とする。

$N$ 回の操作後、$1$ が書かれているマスの個数を $998244353$ で割った余りを求めてください。

ただし、問題文中の $\mathrm{and}$ はビットごとの論理積、$\mathrm{xor}$ は排他的論理和とします。

入力

$N\ K$

  • 入力は全て整数である。
  • $0 \le N,K \le 10^{18}$

出力

$N$ 回の操作後、$1$ が書かれているマスの個数を $998244353$ で割った余りを出力してください。

サンプル

サンプル1
入力
1 0
出力
3

$N=1,K=0$ の場合は、以下の図のようになります。左が初期状態、右が $1$ 回操作した後です。

奇数が書かれているマスは $(0,0)$ と $(0,1)$ と $(1,0)$ の $3$ 個です。

表ではグリッドは $3 \times 3$ で書かれていますが、実際は無限に広がっていることに注意してください。

$\ 1\ $$\ 0\ $$\ 0\ $
$\ 0\ $$\ 0\ $$\ 0\ $
$\ 0\ $$\ 0\ $$\ 0\ $
$\ 1\ $$\ 1\ $$\ 0\ $
$\ 1\ $$\ 0\ $$\ 0\ $
$\ 0\ $$\ 0\ $$\ 0\ $

サンプル2
入力
1 1
出力
4

$N=1,K=1$ の場合は、以下の図のようになります。左が初期状態、右が $1$ 回操作した後です。

奇数が書かれているマスは $(0,0)$ と $(0,2)$ と $(1,0)$ と $(1,1)$ の $4$ 個です。

表ではグリッドは $3 \times 3$ で書かれていますが、実際は無限に広がっていることに注意してください。

$\ 1\ $$\ 1\ $$\ 0\ $
$\ 0\ $$\ 0\ $$\ 0\ $
$\ 0\ $$\ 0\ $$\ 0\ $
$\ 1\ $$\ 0\ $$\ 1\ $
$\ 1\ $$\ 1\ $$\ 0\ $
$\ 0\ $$\ 0\ $$\ 0\ $

サンプル3
入力
3 0
出力
9

$N=3,K=0$ の場合は、以下の図のようになります。左が初期状態で、$1$ 回操作するごとに右のようになります。

$\ 1\ $$\ 0\ $$\ 0\ $$\ 0\ $
$\ 0\ $$\ 0\ $$\ 0\ $$\ 0\ $
$\ 0\ $$\ 0\ $$\ 0\ $$\ 0\ $
$\ 0\ $$\ 0\ $$\ 0\ $$\ 0\ $
$\ 1\ $$\ 1\ $$\ 0\ $$\ 0\ $
$\ 1\ $$\ 0\ $$\ 0\ $$\ 0\ $
$\ 0\ $$\ 0\ $$\ 0\ $$\ 0\ $
$\ 0\ $$\ 0\ $$\ 0\ $$\ 0\ $
$\ 1\ $$\ 0\ $$\ 1\ $$\ 0\ $
$\ 0\ $$\ 0\ $$\ 0\ $$\ 0\ $
$\ 1\ $$\ 0\ $$\ 0\ $$\ 0\ $
$\ 0\ $$\ 0\ $$\ 0\ $$\ 0\ $
$\ 1\ $$\ 1\ $$\ 1\ $$\ 1\ $
$\ 1\ $$\ 0\ $$\ 1\ $$\ 0\ $
$\ 1\ $$\ 1\ $$\ 0\ $$\ 0\ $
$\ 1\ $$\ 0\ $$\ 0\ $$\ 0\ $

サンプル4
入力
123456789 2021
出力
180846079

$998244353$ で割った余りを出力してください。

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