問題一覧 > 通常問題

No.2503 Typical Path Counting Problem on a Grid

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 32
作問者 : suisensuisen / テスター : 👑 emthrmemthrm torisasami4torisasami4 rniyarniya
5 ProblemId : 9928 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-07-25 00:32:03

問題文

非負整数 $n,m$ が与えられます。

二次元平面上の矩形領域 $R$ を $R\coloneqq\lbrace (x,y)\mid 0 \leq x\leq n,\ 0\leq y\leq m\rbrace$ で定めます。

はじめ、suisen 君は点 $(0, 0)\in R$ にいます。

suisen 君は以下の行動を点 $(n, m)\in R$ に到達するまで任意の回数 ($0$ 回でもよい) 繰り返します。

  • 現在 suisen 君がいる点を $(x, y)\in R$ として、以下のいずれか $1$ つを選び実行する:

    1. 点 $(x + 1, y - 1)$ に移動する。
    2. 点 $(x + 1, y)$ に移動する。
    3. 点 $(x + 1, y + 1)$ に移動する。
    4. 点 $(x, y + 1)$ に移動する。
    5. 点 $(x - 1, y + 1)$ に移動する。

    ただし、$R$ に含まれない点への移動や、$1$ 度訪れたことのある点への移動は禁止されています。

suisen 君が点 $(n, m)\in R$ に到達するまでの行動のしかたが何通りあるかを求め、$998244353$ で割った余りを出力してください。

$T$ 個のテストケースが与えられるので、その全てに対して上記の問題を解いてください。

入力

入力は標準入力から以下の形式で与えられる。

まず、$1$ 行目にテストケースの個数 $T$ が以下の形式で与えられる。

$T$

$i + 1\ (1\leq i\leq T)$ 行目には $i$ 個目のテストケースを表す整数 $n, m$ が以下の形式で与えられる。

$n\ m$
  • 入力は全て整数で与えられる。
  • $1 \leq T\leq 2\times 10 ^ 4$
  • $0 \leq n\leq 10 ^ 7$
  • $0 \leq m\leq \textcolor{red}{10 ^ {18}}$

出力

$T$ 行出力してください。$i \ (1\leq i\leq T)$ 行目には、$i$ 個目のテストケースに対する答えを $998244353$ で割った余りを出力してください。

$T$ 行目の出力のあとも改行してください。

サンプル

サンプル1
入力
4
1 1
0 0
10 20
10000000 1000000000000000000
出力
5
1
839227761
950133829

  • 1 つ目のテストケースについて

    $n = 1, m = 1$ を表します。suisen 君の行動のしかたとして考えられるのは、以下の $5$ 通りです。従って、$5$ を出力してください。

    • $(0, 0) \overset{\text{行動}2}{\longrightarrow} (1, 0) \overset{\text{行動}4}{\longrightarrow} (1,1)$
    • $(0, 0) \overset{\text{行動}2}{\longrightarrow} (1, 0) \overset{\text{行動}5}{\longrightarrow} (0,1) \overset{\text{行動}2}{\longrightarrow} (1,1)$
    • $(0, 0) \overset{\text{行動}3}{\longrightarrow} (1, 1)$
    • $(0, 0) \overset{\text{行動}4}{\longrightarrow} (0, 1)\overset{\text{行動}2}{\longrightarrow} (1, 1)$
    • $(0, 0) \overset{\text{行動}4}{\longrightarrow} (0, 1)\overset{\text{行動}1}{\longrightarrow} (1, 0) \overset{\text{行動}4}{\longrightarrow} (1, 1)$

    ここで、$(0, 0) \overset{\text{行動}2}{\longrightarrow} (1, 0) \overset{\text{行動}5}{\longrightarrow} (0,1) \overset{\text{行動}1}{\longrightarrow} (1,0) \overset{\text{行動}4}{\longrightarrow} (1,1)$ のような移動経路は、点 $(1,0)$ を複数回訪れているため許容されません。

    また、$(0,0) \overset{\text{行動}1}{\longrightarrow} (1,-1) \overset{\text{行動}4}{\longrightarrow} (1,0) \overset{\text{行動}4}{\longrightarrow} (1,1)$ のような移動経路は、$R$ に含まれない点 $(1,-1)$ を通っているため許容されません。

  • 2 つ目のテストケースについて

    $n = 0, m = 0$ を表します。$1$ 度も行動しないような場合も許容されるので、このケースの答えは $1$ となります。

  • 3 つ目のテストケースについて

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

  • 4 つ目のテストケースについて

    $m$ は 32 bit 整数型で表現できない可能性があります。

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