問題一覧 > 通常問題

No.2475 Distance Permutation

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 8
作問者 : nok0 / テスター : akakimidori りあん tsutaj beet 👑 tute7627 👑 SPD_9X2 👑 rin204 だれ momoyuu KKT89
0 ProblemId : 10098 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-09-22 12:15:18

問題文

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

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

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

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

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

    • 制約

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

    入力

    KK QQ
query1\mathrm{query}_1
⋮\vdots
queryQ\mathrm{query}_Q

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

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

    NN LL RR

    出力

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

    サンプル

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

    11 個目のクエリで条件を満たす数列は以下の 44 個です。

    • (1,2,3,4)(1,2,3,4)
    • (1,2,4,3)(1,2,4,3)
    • (1,3,2,4)(1,3,2,4)
    • (1,3,4,2)(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もしくは右上の雲マークをクリックしてアカウントを作成してください。