看电影
Time Limit: 10 Sec Memory Limit: 259 MB
Description
到了难得的假期，小白班上组织大家去看电影。但由于假期里看电影的人太多，很难做到让全班看上同一场电影，最后大家在一个偏僻的小胡同里找到了一家电影院。但这家电影院分配座位的方式很特殊，具体方式如下： 1. 电影院的座位共有K个，并被标号为1…K，每个人买完票后会被随机指定一个座位，具体来说是从1…K中等可能的随机选取一个正整数，设其为L。 2. 如果编号L的座位是空位，则这个座位就分配给此人，否则将L加一，继续前面的步骤。 3. 如果在第二步中不存在编号L的座位，则该人只能站着看电影，即所谓的站票。小白班上共有N人（包括小白自己），作为数学爱好者，小白想知道全班都能够有座位的概率是多少。
输入文件第一行有且只有一个正整数T，表示测试数据的组数。 第2～T+1行，每行两个正整数N,K，用单个空格隔开，其含义同题目描述。
Output
输出文件共包含T行。第i行应包含两个用空格隔开的整数A,B，表示输入文件中的第i组数据的答案为A/B。（注意，这里要求将答案化为既约分数）
3
1 1
2 1
2 2
Sample Output
1 1
0 1
3 4
HINT
对于100%的数据 T<=50,N,K<=200
Main idea
有n个人，k个位置，询问按照以下坐法使得所有人都有位置坐的概率是多少。（坐法：每个人随机一个位置，如果这个位置有人那一直就往后坐，如果后面都有人了则不可行）
Source
运用组合数学，首先我们知道n个人k个位置的总方案数是k^n，然后我们考虑一下怎么求出可行的方案，发现直接做的话无解与有解的两个情况不好考虑，怎么办呢？
我们发现可以考虑一下多加一个空位置使其构成一个环，那么这时候每个位置都必定是有解的，方案数就是(k+1)^n。再考虑如何删掉重复的情况，由于我们加入了一个位置，那么除去经过这个位置的情况显然是方案数/(k+1)，那么现在方案数就是(k+1)^n/(k+1)，然后乘上有几个空位置即可。最后答案就是：( (k+1)^n/(k+1)*(k+1-n) ) / (k^n)。
我们发现这个现在求出来的方案数比较大，但是又看见了n,k<=200，想到了数字n的质因数和n^k的质因数是一样的（所以这时候质因数肯定都是200以内的质数），所以我们乘的时候直接质因数分解，然后两个数字的质因数去重，最后用一个高精度乘起来输出即可。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
| #include<bits/stdc++.h>
using namespace std;
const int ONE=201;
int T;
int n,k;
int prime[ONE],cnt;
int p[ONE][3];
int record,x;
struct power
{
int num[10001],len;
void print()
{
for(int i=len;i>=1;i--)
printf("%d",num[i]);
}
friend power operator *(power a,power b)
{
power c;
c.len=a.len+b.len;
for(int i=1;i<=c.len;i++) c.num[i]=0;
for(int i=1;i<=a.len;i++)
{
x=0;
for(int j=1;j<=b.len;j++)
{
c.num[i+j-1]=c.num[i+j-1] + x + a.num[i]*b.num[j];
x=c.num[i+j-1]/10;
c.num[i+j-1]%=10;
}
c.num[i+b.len]=x;
}
while(c.len>1 && !c.num[c.len]) c.len--;
return c;
}
}kd[3],pass;
void dealwith(int x)
{
for(int i=1;i<=pass.len;i++) pass.num[i]=0;
pass.len=0;
while(x)
{
pass.num[++pass.len]=x%10;
x/=10;
}
}
int get()
{
int res=1,Q=1;char c;
while( (c=getchar())<48 || c>57 )
if(c=='-')Q=-1;
res=c-48;
while( (c=getchar())>=48 && c<=57 )
res=res*10+c-48;
return res*Q;
}
int PD(int x)
{
for(int i=2;i<x;i++)
if(x%i==0) return 0;
return 1;
}
int Chai(int x,int PD)
{
if(x==1) return x;
for(int i=1;i<=cnt;i++)
{
if(!(x%prime[i]))
{
p[prime[i]][PD]++;
x=Chai(x/prime[i],PD);
break;
}
}
return x;
}
int Deal(int x,int m,int PD)
{
record=1;
for(int i=1;i<=m;i++)
{
record*=x;
record=Chai(record,PD);
}
if(PD==1)
{
record*=(x-m-1);
record=Chai(record,PD);
}
p[record][PD]++;
}
int main()
{
T=get();
for(int i=2;i<=200;i++)
if(PD(i)) prime[++cnt]=i;
while(T--)
{
n=get(); k=get();
if(n>k)
{
printf("0 1\n");
continue;
}
memset(p,0,sizeof(p));
Deal(k+1,n-1,1); Deal(k,n,2);
for(int i=1;i<=200;i++)
{
int x=min(p[i][1],p[i][2]);
p[i][1]-=x; p[i][2]-=x;
}
kd[1].len=kd[2].len=1;
kd[1].num[1]=kd[2].num[1]=1;
for(int i=1;i<=cnt;i++)
{
dealwith(prime[i]);
for(int t=1;t<=2;t++)
for(int j=1;j<=p[prime[i]][t];j++)
kd[t]=kd[t]*pass;
}
kd[1].print(); printf(" ");
kd[2].print(); printf("\n");
}
}
|
