题目背景

题目描述
小 S 不喜欢集合,不喜欢自然数,不喜欢求和,不喜欢求积,不喜欢最小值,不喜欢最大值,不喜欢 mex,所以有了这题。
给出 n,k,求有多少个可重整数集合 S 满足:
- ∣S∣=k;
- 对于任意 x∈S,0≤x≤n;
- x∈S∏x=x∈Sminx;
- x∈S∑x=x∈Sminx+x∈Smaxx+mex(S)。
注: mex 指集合中没有出现过的最小的自然数。
输入格式
本题包含多组测试数据。
输入的第一行包含一个正整数 T,表示测试数据组数。
对于每组测试数据,输入包含一行两个正整数 n,k。
输出格式
对于每组测试数据,输出一行一个整数表示答案。
提示
【补充说明】
为了更好的让选手理解题面,给出若干合法/不合法集合例子:
- {0,1,2,2}。
该集合是一个符合要求的集合,因为 0×1×2×2=0=min{0,1,2,2},0+1+2+2=5,min{0,1,2,2}+max{0,1,2,2}+mex{0,1,2,2}=0+2+3=5。
该集合不是一个符合要求的集合,因为虽然 3+5=8,min{3,5}+max{3,5}+mex{3,5}=3+5+0=8,但是 3×5=min{3,5}。
- {1,9,1,9,8,1,0}。
该集合不是一个符合要求的集合,因为虽然 1×9×1×9×8×1×0=0=min{1,9,1,9,8,1,0},但是其和为 29 而并非 min+max+mex=0+9+2=11。
【数据范围】
对于 100% 的数据,保证 1≤T≤106,1≤n,k≤1018。
测试点编号 |
分值 |
T≤ |
k≤ |
n |
1 |
10 |
5 |
≤5 |
2 |
105 |
1018 |
=1 |
3 |
=2 |
4 |
=3 |
5 |
=4 |
6 |
=5 |
7 |
10 |
≤10 |
8 |
103 |
≤103 |
9 |
106 |
1018 |
≤108 |
10 |
≤1018 |