問題一覧 > 通常問題

No.1531 Ku 2

レベル : / AI推定難易度 : 2225 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 27
作問者 : PCTprobability / テスター : tatyam ngtkana
お気に入りにしたユーザー ProblemId : 6444 / 自分の提出
問題文最終更新日: 2021-06-04 15:55:50
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 298 (順位表) の他の問題:

Problem Statement

There is a $2$-dimensional grid that extends infinitely to the right and downward.

The cell in the $i$-th row from the top and the $j$-th column from the left is called $(i,j)$.

Every cell has $1$ non-negative integer written on it. The integer written on $(i,j)$ is $A_{i,j}$.

Initially, $A_{0,i}=1$ for each non-negative integer $i$ satisfying $K\ \mathrm{and}\ i=i$. For all other cells, $A_{p,q}=0$.

Perform the following operation $N$ times.

  • Simultaneously for all cells, replace the written integer with its $\mathrm{xor}$ with the cells to the left and above. Formally, simultaneously for all cells $(i,j)$, replace $A_{i,j}$ with $A_{i,j}\ \mathrm{xor}\ A_{i-1,j}\ \mathrm{xor}\ A_{i,j-1}$. Here, $A_{-1,i}=A_{i,-1}=0$.

Find the number of cells with $1$ written on them after the $N$ operations, modulo $998244353$.

In this statement, $\mathrm{and}$ denotes the bitwise AND and $\mathrm{xor}$ denotes the bitwise exclusive OR.

Input

$N\ K$

  • All inputs are integers.
  • $0 \le N,K \le 10^{18}$

Output

Output the number of cells with $1$ written on them after the $N$ operations, modulo $998244353$.

Sample

Sample 1
Input
1 0
Output
3

The case $N=1,K=0$ is shown in the figure below. The left is the initial state and the right is after $1$ operation.

There are $3$ cells with an odd number written on them: $(0,0)$, $(0,1)$, and $(1,0)$.

Note that although the grid is drawn as $3 \times 3$ in the tables, it actually extends infinitely.

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

Sample 2
Input
1 1
Output
4

The case $N=1,K=1$ is shown in the figure below. The left is the initial state and the right is after $1$ operation.

There are $4$ cells with an odd number written on them: $(0,0)$, $(0,2)$, $(1,0)$, and $(1,1)$.

Note that although the grid is drawn as $3 \times 3$ in the tables, it actually extends infinitely.

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

Sample 3
Input
3 0
Output
9

The case $N=3,K=0$ is shown in the figure below. The leftmost is the initial state, and each $1$ operation moves one table to the right.

$\ 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\ $

Sample 4
Input
123456789 2021
Output
180846079

Output the remainder when divided by $998244353$.

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