#P17213. [2025年海亮中学]约瑟夫问题

    ID: 16372 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>CF2600省选/NOI-分段多项式等差数列求和向下取整与向上取整交换求和顺序模逆元

[2025年海亮中学]约瑟夫问题

题目描述

有 nn 个人,编号为 11 到 nn,坐在环上玩约瑟夫。

他们从 11 到 mm 循环报数,与正常约瑟夫不同的是,没有报到 11 的人都会被淘汰,直至只有一个人活下来为止。

设活下来的人编号为 xx,则记 Jm(n)=xJ_m(n)=x。

给定 m,l,rm,l,r,求 ∑i=lrJm(i)\sum_{i=l}^{r}J_m(i),输出对 998244353998244353 取模。

输入格式

本题有多组数据。

第一行一个正整数 TT,表示数据组数。

对于每组数据:

一行三个整数,依次为 m,l,rm,l,r。

输出格式

对于每组数据:

输出一行一个整数,表示答案对 998244353998244353 取模的结果。

输入输出样例 #1

输入 #1

4
2 1 4
3 3 7
8 12 64
2 1 1048976

输出 #1

6
17
1149
148359175

说明/提示

本题采用捆绑测试。

  • Subtask 1(4 pts):T=1T=1,m≤10m \leq 10,r≤200r \leq 200。
  • Subtask 2(8 pts):T=1T=1,m≤106m \leq 10^6,r≤107r\leq 10^7。
  • Subtask 3(8 pts):∑(r−l+1)≤2×106\sum (r-l+1) \leq 2 \times 10^6。
  • Subtask 4(10 pts):m=2m=2。
  • Subtask 5(25 pts):T≤5T \leq 5,m≤106m \leq 10^6。
  • Subtask 6(45 pts):无特殊限制。

对于 100%100\% 的数据,1≤T≤1041 \leq T \leq 10^4,2≤m≤10122 \leq m \leq 10^{12},1≤l≤r≤10181 \leq l \leq r \leq 10^{18}。