题目描述
到了难得的假期，小白班上组织大家去看电影。但由于假期里看电影的人太多，很难做到让全班看上同一场电影，最后大家在一个偏僻的小胡同里找到了一家电影院。但这家电影院分配座位的方式很特殊，具体方式如下：
电影院的座位共有K个，并被标号为1...K，每个人买完票后会被随机指定一个座位，具体来说是从1...K中等可能的随机选取一个正整数，设其为L。
如果编号L的座位是空位，则这个座位就分配给此人，否则将L加一，继续前面的步骤。
- 如果在第二步中不存在编号L的座位，则该人只能站着看电影，即所谓的站票。
小白班上共有N人（包括小白自己），作为数学爱好者，小白想知道全班都能够有座位的概率是多少。
输入输出格式
输入格式：
输入文件第一行有且只有一个正整数T，表示测试数据的组数。 第2～T+1行，每行两个正整数N,K，用单个空格隔开，其含义同题目描述。
输出格式：
输出文件共包含T行。第i行应包含两个用空格隔开的整数A,B，表示输入文件中的第i组数据的答案为A/B。（注意，这里要求将答案化为既约分数）
输入输出样例
输入样例#1：
3
1 1
2 1
2 2
输出样例#1：
1 1
0 1
3 4
范围
0<=n,k<=200
题解
组合数学加高精度
首先这是一个古典概型，概率等于合法的方案数除以总方案数。总方案数=K^N
合法方案数的计算：在最后面加一个座位，然后所有的座位连成一个环。现在那么总方案数等于(K+1)N，
每种环都算了(K+1)次，所以除以(K+1)，最后抽调一个空白的座位来构造一个合法的方案，所以要乘(N−K+1)。
ans=(K+1）^(N-1)*(K-N+1)/K^N
高精度用十位一进
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
long long w=1e9;
long long c[],s1[],s2[],len1,len2;
void chen1(int k)
{int i;
memset(c,,sizeof(c));
for (i=;i<=len1;i++)
{
c[i]+=s1[i]*k;
if (c[i]>=w)
{
c[i+]+=c[i]/w;
c[i]%=w;
}
}
if (c[len1+]) len1++;
while (c[len1]>=w)
{
c[len1+]+=c[len1]/w;
c[len1]%=w;
len1++;
}
for (i=;i<=len1;i++)
{
s1[i]=c[i];
}
}
void chen2(int k)
{int i;
memset(c,,sizeof(c));
for (i=;i<=len2;i++)
{
c[i]+=s2[i]*k;
if (c[i]>=w)
{
c[i+]+=c[i]/w;
c[i]%=w;
}
}
if (c[len2+]) len2++;
while (c[len2]>=w)
{
c[len2+]+=c[len2]/w;
c[len2]%=w;
len2++;
}
for (i=;i<=len2;i++)
{
s2[i]=c[i];
}
}
void epow1(int x,int y)
{int i;
for (i=;i<=y;i++)
chen1(x);
}
void epow2(int x,int y)
{int i;
for (i=;i<=y;i++)
chen2(x);
}
void print1()
{int i,j;
printf("%lld",s1[len1]);
for (i=len1-;i>=;i--)
{int k=;
long long x=s1[i];
while (x)
{k++;
x/=;
}
for (j=;j>k;j--)
printf("");
if (s1[i])
printf("%lld",s1[i]);
}
}
void print2()
{int i,j;
printf("%lld",s2[len2]);
for (i=len2-;i>=;i--)
{int k=;
long long x=s2[i];
while (x)
{k++;
x/=;
}
for (j=;j>k;j--)
printf("");
if (s2[i])
printf("%lld",s2[i]);
}
}
long long gcd(long long a,long long b)
{
if (b==)
{
return a;
}
long long r=gcd(b,a%b);
return r;
}
int main()
{int T,l,i,n,k;
//freopen("ans.out","w",stdout);
cin>>T;
for (l=;l<=T;l++)
{
scanf("%d%d",&n,&k);
if (n>k)
{
cout<<<<' '<<<<endl;
continue;
}
memset(s1,,sizeof(s1));
memset(s2,,sizeof(s2));
s1[]=;
len1=;
long long x=k-n+;
for (i=;i<=n;i++)
{
long long d=gcd(k,x);
x/=d;
chen1(k/d);
}
len2=;
s2[]=;
epow2(k+,n-);
chen2(x);
print2();
cout<<' ';
print1();
cout<<endl;
}
}