Description
到了难得的假期，小白班上组织大家去看电影。但由于假期里看电影的人太多，很难做到让全班看上同一场电影，最后大家在一个偏僻的小胡同里找到了一家电影院。但这家电影院分配座位的方式很特殊，具体方式如下： 1. 电影院的座位共有K个，并被标号为1…K，每个人买完票后会被随机指定一个座位，具体来说是从1…K中等可能的随机选取一个正整数，设其为L。 2. 如果编号L的座位是空位，则这个座位就分配给此人，否则将L加一，继续前面的步骤。 3. 如果在第二步中不存在编号L的座位，则该人只能站着看电影，即所谓的站票。小白班上共有N人（包括小白自己），作为数学爱好者，小白想知道全班都能够有座位的概率是多少。
Input
输入文件第一行有且只有一个正整数T，表示测试数据的组数。 第2～T+1行，每行两个正整数N,K，用单个空格隔开，其含义同题目描述。
Output
输出文件共包含T行。第i行应包含两个用空格隔开的整数A,B，表示输入文件中的第i组数据的答案为A/B。（注意，这里要求将答案化为既约分数）
Sample Input
1 1
2 1
2 2
Sample Output
1 1
0 1
3 4
【数据范围】
对于100%的数据 T<=50,N,K<=200
其实这题正解是打表找规律
首先我们一定是把所有方案数作为分母，
显然是$k^n$
另外当$n>k$时输出0 1即可
之后的思路就比较神仙
我们把链转成环，并在最后加一个座位
这样根据题目给定的规则，由于$n<k$，每个人最后一定可以坐下
如果有人走到座位$k$都不能坐下，他就会在加的那个座位坐下
那么一个合法方案 即加的座位没有人坐的情况
这时候就可以开始列柿子了
$n$个人，每次选$k+1$中的一个坐下（反正最终一定能坐下，不用想的太复杂）,$(k+1)^n$
且因为环的性质（哪都能断，可能重复），每种排列算了k+1次
所以这部分是$\frac{(k+1)^n}{k+1}=(k+1)^{n-1}$
且有$k-n+1$个空着的
我们可以选择从这些位置断开重新伸展成链，使第$k+1$个座无意义化
$ANS=\frac{(k+1)^{n-1}(k-n+1)}{k^n}$
没模法显然要高精对吧
（高精乘低精就搞定了）
这道题还要求输出约分后的结果别告诉我你要高精除
分母累乘的时候一直求gcd一直约就行了
（快速幂什么的都去死吧）
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int T,n,k,num1[],num2[],n1;
void mult(int x,int a[])
{
int k=;
for(int i=;i<=a[];i++)
{
int tmp=a[i]*x+k;
a[i]=tmp%;
k=tmp/;
}
while(k)a[++a[]]=k%,k/=;
}
int gcd(int x,int y)
{
if(!y)return x;
return gcd(y,x%y);
}
void work()
{
scanf("%d%d",&n,&k);
memset(num1,,sizeof(num1));
memset(num2,,sizeof(num2));
num1[]=num1[]=num2[]=num2[]=;
if(n>k)
{
puts("0 1");
return ;
}
n1=k-n+;
for(int i=;i<=n-;i++)
mult(k+,num1);
for(int i=;i<=n;i++)
{
int now=k,GCD=gcd(k,n1);
if(GCD!=)
{
now/=GCD;
n1/=GCD;
}
mult(now,num2);
}
mult(n1,num1);
for(int i=num1[];i;i--)
printf("%d",num1[i]);
printf(" ");
for(int i=num2[];i;i--)
printf("%d",num2[i]);
puts(" ");
}
int main()
{
scanf("%d",&T);
while(T--)work();
return ;
}