题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2227
组合数学，加上一个位置，可以看成是一个环，方案数(k+1)^n，是环就可以转，那么就有k+1个方案重复，故实际方案数为(k+1)^(n-1)，再把这个位置去掉，方案数为k+1-n，所以对于这个问题本身来说，方案数为(k+1)^n·(k+1)^(n-1)，总方案数为k^n，则概率为方案数/总方案数。
关于输出，因为要约分来着，这题显然需要高精度，就直接分解质因子即可。但是事实上k+1和k互质，所以可以直接把k+1-n拎出来约分就好了。
输出可以压位，但实际上不压位也能过，但是一定要注意输出长度！
贴代码
const tt=10;maxn=205; type arr=array[0..600]of longint; var n,k,x,y,Q,dt,i,j,t:longint; ans1,ans2:arr; vis:array[0..maxn]of boolean; prime,g,f:array[0..50]of longint; function mul(a,b:arr):arr; var i,j:longint; c:arr; begin fillchar(c,sizeof(c),0); c[0]:=a[0]+b[0]; for i:=1 to a[0] do for j:=1 to b[0] do begin inc(c[i+j-1],a[i]*b[j]); inc(c[i+j],c[i+j-1] div tt); c[i+j-1]:=c[i+j-1] mod tt; end; while (c[c[0]]=0)and(c[0]>1) do dec(c[0]); exit(c); end; function power(a,b:longint):arr; var s,w:arr; begin s[0]:=1;s[1]:=1; if trunc(ln(a)/ln(10))+1=1 then begin w[0]:=1;w[1]:=a; end; if trunc(ln(a)/ln(10))+1=2 then begin w[0]:=2;w[2]:=a div 10;w[1]:=a mod 10; end; if trunc(ln(a)/ln(10))+1=3 then begin w[0]:=3;w[3]:=a div 100;w[2]:=(a div 10) mod 10;w[1]:=a mod 10; end; while b<>0 do begin if b and 1=1 then s:=mul(s,w); w:=mul(w,w); b:=b>>1; end; exit(s); end; begin assign(input,'movie.in');reset(input); assign(output,'movie.out');rewrite(output); fillchar(vis,sizeof(vis),1); for i:=2 to trunc(sqrt(maxn)) do if vis[i] then for j:=2 to maxn div i do vis[i*j]:=false; prime[0]:=0; for i:=2 to maxn do if vis[i] then begin inc(prime[0]); prime[prime[0]]:=i; end; readln(Q); for t:=1 to Q do begin readln(n,k); if k+1-n<=0 then begin writeln(0,' ',1);continue; end; fillchar(g,sizeof(g),0); fillchar(f,sizeof(f),0); for i:=1 to prime[0] do begin if (k+1)mod prime[i]=0 then begin x:=k+1; while x mod prime[i]=0 do begin inc(g[i],n-1); x:=x div prime[i]; end; end; if (k+1-n)mod prime[i]=0 then begin x:=k+1-n; while x mod prime[i]=0 do begin inc(g[i]); x:=x div prime[i]; end; end; if k mod prime[i]=0 then begin x:=k; while x mod prime[i]=0 do begin inc(f[i],n); x:=x div prime[i]; end; end; end; ans1[0]:=1;ans1[1]:=1; ans2[0]:=1;ans2[1]:=1; for i:=1 to prime[0] do begin if f[i]<g[i] then dt:=f[i] else dt:=g[i]; dec(f[i],dt);dec(g[i],dt); if g[i]<>0 then ans1:=mul(ans1,power(prime[i],g[i])); if f[i]<>0 then ans2:=mul(ans2,power(prime[i],f[i])); end; for i:=ans1[0] downto 1 do write(ans1[i]); write(' '); for i:=ans2[0] downto 1 do write(ans2[i]);writeln; end; close(input);close(output); end. 【写的有漏洞的，欢迎路过大神吐槽】2017/3/13 14:16:05
Ending.
