现在的位置: 首页 > 综合 > 正文

看电影(movie)

2018年01月15日 ⁄ 综合 ⁄ 共 2231字 ⁄ 字号 评论关闭

看电影(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.
【上篇】
【下篇】

抱歉!评论已关闭.