#P17925. Hashing
Hashing
Hashing
题目描述
对于一棵有根树,记 为顶点 的子树大小, 为 的所有孩子构成的集合。
给定任意映射 ,递归定义哈希值:
$$h(u)=1+\sum_{v\in\operatorname{son}_u}h(v)f(\operatorname{sz}_v).$$整棵树的哈希值是根的哈希值,单点树的哈希值为 。这里的计算使用整数,不对任何模数取模。
若存在同一个映射 ,使两棵有根树得到不同的哈希值,则称这两棵树可区分;若对所有映射 ,二者哈希值均相同,则称它们不可区分。
求最多能选出多少棵恰有 个顶点的有根二叉树,使选出的树两两可区分。有根二叉树指每个顶点至多有两个孩子的有根树。
只需将这个最大数量对给定的 取模后输出。 仅用于最终计数,不用于上述哈希值的定义。
输入格式
第一行一个整数 ,表示测试数据组数。
接下来 行,每行两个整数 。
输出格式
每组数据输出一行一个整数,表示答案对 取模的结果。
数据范围
- ,。
- ,不保证 为质数。
- 所有测试数据的 之和不超过 。
样例
8
1 1000000009
5 1000000009
10 1000000009
15 1000000009
100 1000000009
150 1000000009
1000 1000000009
1500 1000000009
1
6
207
10904
478868953
202933416
152259136
264735211