No.2132 1 or X Game
タグ : / 解いたユーザー数 56
作問者 :
nok0
/ テスター :
ぷら
taiga0629kyopro
Problem Statement
We call the following game Game $n$.
Alice and Bob play a game. Initially, there are $n$ stones.
Starting with Alice, they take turns alternately, each choosing and performing one of the following operations. The player who cannot perform an operation loses.
- Remove $1$ stone.
- Remove $X$ stones. If a player chooses this operation, that player cannot choose this operation on their next turn.
Among Game $1$, Game $2$, …, Game $N$, find the number of games that Alice wins when both players play optimally.
The answer is not very large and fits in a 64-bit integer type, but since we have the chance, output it modulo $998244353$.
For each input file, answer $T$ test cases.
Constraints
- All inputs are integers
- $1 \le T\le 2\times 10^5$
- $1 \le N,X \le 10^{18} $
Input
The input is given from standard input in the following format.$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
Each test case is given in the following format.
$N$ $X$
Output
Output $T$ lines.
On the $i$-th line $(1\leq i \leq T)$, output the answer to the $i$-th test case modulo $998244353$.
Sample
Sample 1
Input
3 4 3 1 1 10000000000 99999999
Output
2 1 8778235
In the $1$-st test case, Alice wins Game $1$ and Game $3$. In Game $1$ she should first remove $1$ stone, and in Game $3$ she should first remove $3$ stones.
In the $3$-rd test case, the answer is $5000000000$, but note that you must output it modulo $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。