問題一覧 > 通常問題

No.2475 Distance Permutation

レベル : / AI推定難易度 : 2950 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 8
作問者 : nok0 / テスター : akakimidori りあん tsutaj beet 👑 tute7627 SPD_9X2 👑 rin204 だれ momoyuu KKT89
お気に入りにしたユーザー ProblemId : 10098 / 自分の提出
問題文最終更新日: 2023-09-22 12:15:18
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
Japan Alumni Group Summer Camp 2023 Day 2 (順位表) の他の問題:

Problem Statement

You construct a permutation $ P=(P_1,P_2,\ldots,P_{10^5})$ of length $ 10^5$ in the following way.

There are points $ 1,2,\ldots,10^5$ on a number line. The distance between points $ i$ and $ j$ is $ |i-j|$. There is also a sequence $ P$, which is initially empty. Starting from any point of your choice, repeat the following operation until the length of $ P$ becomes $ 10^5$.

    　
  • Let $ x$ be the number of the current point. If $ x$ is not contained in $ P$, append $x$ to the end of $ P$. Then, move to a point at distance at most $ K$.

Answer the following $ Q$ queries.

  • You are given integers $ N,L,R$. Let $ P'=(P'_1,P'_2,\ldots,P'_N)$ be the sequence obtained by removing the elements greater than $ N$ from $ P$. Among the permutations possible as $ P'$, find the number of those whose $ P'_1$ is between $ L$ and $ R$, inclusive, modulo $\text{mod }998244353$.

    • Constraints

    • All inputs are integers.
    • $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$

    Input

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

    Here, $\mathrm{query}_i$ denotes the $i$-th query.

    Each query is given in the following format.

    $N$ $L$ $R$

    Output

    Print $Q$ lines. The $i$-th line should contain the answer to the $i$-th query.

    Sample

    Sample 1
    Input
    2 4
4 1 1
3 1 3
10 2 7
1 1 1
    Output
    4
6
140172
1

    The $4$ sequences satisfying the condition in the $1$-st query are as follows.

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

    Sample 2
    Input
    314 6
60522 7560 25373
79445 26896 78962
33447 12441 21469
47202 17227 32455
63982 13450 41311
2156 1226 2148
    Output
    925500464
455690352
567782656
893053639
942918900
458845228

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