看电影(movie)
【题目描述】
到了难得的假期,小白班上组织大家去看电影。但由于假期里看电影的人
太多,很难做到让全班看上同一场电影,最后大家在一个偏僻的小胡同里找到了
一家电影院。但这家电影院分配座位的方式很特殊,具体方式如下:
1. 电影院的座位共有K 个,并被标号为1…K,每个人买完票后会被随机指定一个座
位,具体来说是从1…K 中等可能的随机选取一个正整数,设其为L。
2. 如果编号L 的座位是空位,则这个座位就分配给此人,否则将L 加一,继续前面的
步骤。
3. 如果在第二步中不存在编号L 的座位,则该人只能站着看电影,即所谓的站票。
小白班上共有N 人(包括小白自己),作为数学爱好者,小白想知道全班都
能够有座位的概率是多少。
【输入说明】
输入文件第一行有且只有一个正整数T,表示测试数据的组数。
第2~T+1 行,每行两个正整数N,K,用单个空格隔开,其含义同题目描述。
【输出说明】
输出文件共包含T 行。
第i 行应包含两个用空格隔开的整数A,B,表示输入文件中的第i 组数据
的答案为A/B。(注意,这里要求将答案化为既约分数)
【样例输入】
3
1 1
2 1
2 2
【样例输出】
1 1
0 1
3 4
【数据范围】
对于20%的数据N,K<=10
对于100%的数据T<=50,N,K<=200
第一次做这题被虐傻了T__T。。。。
对于求期望,一般是用合法的方案数/总方案数去算。
这题的总方案数是:K^N
现在的问题就是如何求合法的方案数。
注意到题目中那个有趣的规则。
可以发现,一个方案合法等价于第K+1个位置上为空。
那么现在只需求出第K+1个位置为空的方案数
这样子直接想还是不好办。但是可以发现不好办的根源在于往后移动那个规则,移动到第K+1个位置就不合法了。
于是考虑一个长度为K+1的环的情况。
可以发现只要N>K就一定无解,那么现在假设N<=K。
把N个元素放到K+1个位置上有(K+1)^N种方案,每一种方案有K+1-N个空位置。
为了使第K+1个位置为空,那么一定有(K+1)^N*(K+1-N)种方案。
现在环上的问题解决了。对应到原问题,这是一个序列,我们在环上考虑的时候不仅考虑了放的相对顺序,而且还考虑了环上的绝对位置,但实际上这些元素之间是无序的,所以答案还要除以一个K+1。
即:(K+1)^(N-1)*(K+1-N)和K^N
关于即约分数,由于gcd(k+1,k)==1,这个就很好办了。
program movie; type gj=array [0..10001] of longint; var t,n,i,j,k,m:longint; son,mon:gj; count:array [0..201] of longint; procedure mul (var a:gj;b:longint);inline; var i:longint; begin for i:=1 to a[0] do a[i]:=a[i]*b; i:=1; while (i<=a[0])or(a[i]<>0) do begin a[i+1]:=a[i+1]+a[i] div 10; a[i]:=a[i] mod 10; inc(i); end; dec(i); a[0]:=i; end; procedure print (a:gj);inline; var i:longint; begin for i:=a[0] downto 1 do write(a[i]); end; begin assign(input,'movie.in'); reset(input); assign(output,'movie.out'); rewrite(output); read(t); while t>0 do begin dec(t); read(n,k); if n>k then begin writeln(0,' ',1); continue; end; fillchar(count,sizeof(count),0); m:=k+1; for i:=2 to trunc(sqrt(k+1)) do while m mod i = 0 do begin m:=m div i; count[i]:=count[i]+n-1; end; if m>1 then count[m]:=count[m]+n-1; m:=k+1-n; for i:=2 to trunc(sqrt(k+1-n)) do while m mod i = 0 do begin m:=m div i; inc(count[i]); end; if m>1 then inc(count[m]); m:=k; for i:=2 to trunc(sqrt(k)) do while m mod i = 0 do begin m:=m div i; count[i]:=count[i]-n; end; if m>1 then count[m]:=count[m]-n; fillchar(son,sizeof(son),0); son[0]:=1; son[1]:=1; fillchar(mon,sizeof(mon),0); mon[0]:=1; mon[1]:=1; for i:=2 to k+1 do if count[i]>0 then for j:=1 to count[i] do mul(son,i) else if count[i]<0 then for j:=1 to -count[i] do mul(mon,i); print(son); write(' '); print(mon); writeln; end; close(input); close(output); end.