問題一覧 > 通常問題

No.2475 Distance Permutation

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 7
作問者 : nok0nok0 / テスター : akakimidoriakakimidori りあんりあん tsutajtsutaj beetbeet 👑 tute7627tute7627 👑 SPD_9X2SPD_9X2 👑 rin204rin204 だれだれ momoyuumomoyuu KKT89KKT89
0 ProblemId : 10098 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-09-22 12:15:18

問題文

あなたは以下の方法で長さ $ 10^5$ の順列 $ P=(P_1,P_2,\ldots,P_{10^5})$ を作ります。

数直線上に点 $ 1,2,\ldots,10^5$ があります。点 $ i$ と $ j$ の距離は $ |i-j|$ です。また、はじめ空な数列 $ P$ があります。好きな点からはじめ、以下の操作を $ P$ の長さが $ 10^5$ になるまで繰り返します。

    　
  • 今いる点の番号を $ x$ とする。$ x$ が $ P$ に含まれない場合、$ P$ の末尾に $x$ を追加する。その後、距離が $ K$ 以下の点に移動する。

以下の $ Q$ 個のクエリに答えてください。

  • 整数 $ N,L,R$ が与えられる。$ P$ から $ N$ より大きい要素を取り除いてできる数列を $ P'=(P'_1,P'_2,\ldots,P'_N)$ とする。$ P'$ として考えられる順列の中で、$ P'_1$ が $ L$ 以上 $ R$ 以下のものの個数を $\text{mod }998244353$ で求めよ。

    • 制約

    • 入力は全て整数
    • $1 \le Q\le 2\times 10^5$
    • $1 \le K\le 10^5$
    • $1\le N\le 10^5$
    • $1 \le L \le R \le N$

    入力

    $K$ $Q$
$\mathrm{query}_1$
$\vdots$
$\mathrm{query}_Q$

    ただし、$\mathrm{query}_i$ は $i$ 個目のクエリを表す。

    各クエリは以下の形式で与えられる。

    $N$ $L$ $R$

    出力

    $Q$ 行出力せよ。$i$ 行目には、$i$ 個目のクエリに対する答えを出力せよ。

    サンプル

    サンプル1
    入力
    2 4
4 1 1
3 1 3
10 2 7
1 1 1
    出力
    4
6
140172
1

    $1$ 個目のクエリで条件を満たす数列は以下の $4$ 個です。

    • $(1,2,3,4)$
    • $(1,2,4,3)$
    • $(1,3,2,4)$
    • $(1,3,4,2)$

    サンプル2
    入力
    314 6
60522 7560 25373
79445 26896 78962
33447 12441 21469
47202 17227 32455
63982 13450 41311
2156 1226 2148
    出力
    925500464
455690352
567782656
893053639
942918900
458845228

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