【MX-X30-T5】メタモリボン

ID: 19618

远端评测题

1500ms

250MiB

显示难度省选/NOI−

上传者:

标签>

梦熊比赛

背景

考虑将一个非负整数集合中的所有元素的 $B$ 进制表示看作一个字符串集合。令 $R$ 的 $B$ 进制表示长度为 $l$ ，对于集合内的每个字符串，都在开头补 $0$ 直到其长度为 $l$ 。将这些字符串插入到一棵字典树中，并忽略字典树的边权与点的编号得到一棵无权无标号有根树。

给定 $B, L, R$ ，你需要统计所有非空的 $S \subseteq \{L, L + 1, L + 2, \dots, R\}$ 能得到的本质不同的树的数量，答案对 $10^9 + 7$ 取模。

本题有多测，第一行包含一个整数 $T$ 表示测试组数。

接下来 $T$ 行，表示每组测试的三个整数 $B,L,R$ 。

$T$ 行，每行输出一个整数，表示所有非空的 $S \subseteq \{L, L + 1, L + 2, \dots, R\}$ 能得到的本质不同的树的数量，答案对 $10^9 + 7$ 取模。

6
2 1 2
2 1 3
2 3 19
6 1 119
32000 1 1000000000
12 99999994 100000010

子任务编号	分数	$T\le$	$B\le$	特殊性质
$1$	$12$	$5$	$2$	A
$2$	$12$	$5$	$2$	无
$3$	$22$	$10^4$	$100$	无
$4$	$5$	$5$	$10^9$	B
$5$	$22$	$5$		无
$6$	$12$	$10^4$		A
$7$	$5$	$10^4$		无
$8$	$10$	$5\times 10^4$		无

特殊性质 A： $L=0$ 。

特殊性质 B： $R-L\le 10$ 。

对于所有数据， $1 \le T \le 5 \times 10^4$ ， $2 \le B \le 10^9$ ， $0 \le L \le R \le 10^9$ 。