「EZEC-11」Circle

Luogu
IDLGP8181
Time1000ms
Memory128MB
DifficultyP7
数学O2优化洛谷月赛
有 $n$ 个人,编号为 $1$ 到 $n$,坐在环上玩约瑟夫。 他们从 $1$ 到 $m$ 循环报数,与正常约瑟夫不同的是,没有报到 $1$ 的人都会被淘汰,直至只有一个人活下来为止。 设活下来的人编号为 $x$,则记 $J_m(n)=x$。 给定 $m,l,r$,求 $\sum_{i=l}^{r}J_m(i)$,输出对 $998244353$ 取模。 ## Input **本题有多组数据**。 第一行一个正整数 $T$,表示数据组数。 对于每组数据: 一行三个整数,依次为 $m,l,r$。 ## Output 对于每组数据: 输出一行一个整数,表示答案对 $998244353$ 取模的结果。 [samples] ## Note **本题采用捆绑测试。** - Subtask 1(4 pts):$T=1$,$m \leq 10$,$r \leq 200$。 - Subtask 2(8 pts):$T=1$,$m \leq 10^6$,$r\leq 10^7$。 - Subtask 3(8 pts):$\sum (r-l+1) \leq 2 \times 10^6$。 - Subtask 4(10 pts):$m=2$。 - Subtask 5(25 pts):$T \leq 5$,$m \leq 10^6$。 - Subtask 6(45 pts):无特殊限制。 对于 $100\%$ 的数据,$1 \leq T \leq 10^4$,$2 \leq m \leq 10^{12}$,$1 \leq l \leq r \leq 10^{18}$。
Samples
Input #1
4
2 1 4
3 3 7
8 12 64
2 1 1048976
Output #1
6
17
1149
148359175
API Response (JSON)
{
  "problem": {
    "name": "「EZEC-11」Circle",
    "description": {
      "content": "有 $n$ 个人,编号为 $1$ 到 $n$,坐在环上玩约瑟夫。 他们从 $1$ 到 $m$ 循环报数,与正常约瑟夫不同的是,没有报到 $1$ 的人都会被淘汰,直至只有一个人活下来为止。 设活下来的人编号为 $x$,则记 $J_m(n)=x$。 给定 $m,l,r$,求 $\\sum_{i=l}^{r}J_m(i)$,输出对 $998244353$ 取模。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8181"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有 $n$ 个人,编号为 $1$ 到 $n$,坐在环上玩约瑟夫。\n\n他们从 $1$ 到 $m$ 循环报数,与正常约瑟夫不同的是,没有报到 $1$ 的人都会被淘汰,直至只有一个人活下来为止。\n\n设活下来的人编号为 $x$,则记 $J_m(n)=x$。\n\n给定 $m,l,r$,求 $\\sum_{i=l}^{r}J_m(i)$,输出对 $998244353$ 取模。\n\n## Input\n\n**本题有多组...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments