【BZOJ2227】【ZJOI2011】看电影 [组合数][质因数分解]

看电影

Time Limit: 10 Sec  Memory Limit: 259 MB
[Submit][Status][Discuss]

Description

  到了难得的假期,小白班上组织大家去看电影。但由于假期里看电影的人太多,很难做到让全班看上同一场电影,最后大家在一个偏僻的小胡同里找到了一家电影院。但这家电影院分配座位的方式很特殊,具体方式如下: 1. 电影院的座位共有K个,并被标号为1…K,每个人买完票后会被随机指定一个座位,具体来说是从1…K中等可能的随机选取一个正整数,设其为L。 2. 如果编号L的座位是空位,则这个座位就分配给此人,否则将L加一,继续前面的步骤。 3. 如果在第二步中不存在编号L的座位,则该人只能站着看电影,即所谓的站票。小白班上共有N人(包括小白自己),作为数学爱好者,小白想知道全班都能够有座位的概率是多少。

Input

  输入文件第一行有且只有一个正整数T,表示测试数据的组数。 第2~T+1行,每行两个正整数N,K,用单个空格隔开,其含义同题目描述。

Output

  输出文件共包含T行。第i行应包含两个用空格隔开的整数A,B,表示输入文件中的第i组数据的答案为A/B。(注意,这里要求将答案化为既约分数)

Sample Input

  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

 #include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std; const int ONE=; int T;
int n,k;
int prime[ONE],cnt;
int p[ONE][];
int record,x; struct power
{
int num[],len;
void print()
{
for(int i=len;i>=;i--)
printf("%d",num[i]);
} friend power operator *(power a,power b)
{
power c;
c.len=a.len+b.len;
for(int i=;i<=c.len;i++) c.num[i]=; for(int i=;i<=a.len;i++)
{
x=;
for(int j=;j<=b.len;j++)
{
c.num[i+j-]=c.num[i+j-] + x + a.num[i]*b.num[j];
x=c.num[i+j-]/;
c.num[i+j-]%=;
}
c.num[i+b.len]=x;
} while(c.len> && !c.num[c.len]) c.len--;
return c;
}
}kd[],pass; void dealwith(int x)
{
for(int i=;i<=pass.len;i++) pass.num[i]=;
pass.len=;
while(x)
{
pass.num[++pass.len]=x%;
x/=;
}
} int get()
{
int res=,Q=;char c;
while( (c=getchar())< || c> )
if(c=='-')Q=-;
res=c-;
while( (c=getchar())>= && c<= )
res=res*+c-;
return res*Q;
} int PD(int x)
{
for(int i=;i<x;i++)
if(x%i==) return ;
return ;
} int Chai(int x,int PD)
{
if(x==) return x;
for(int i=;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=;
for(int i=;i<=m;i++)
{
record*=x;
record=Chai(record,PD);
} if(PD==)
{
record*=(x-m-);
record=Chai(record,PD);
} p[record][PD]++;
} int main()
{
T=get();
for(int i=;i<=;i++)
if(PD(i)) prime[++cnt]=i; while(T--)
{
n=get(); k=get();
if(n>k)
{
printf("0 1\n");
continue;
} memset(p,,sizeof(p));
Deal(k+,n-,); Deal(k,n,);
for(int i=;i<=;i++)
{
int x=min(p[i][],p[i][]);
p[i][]-=x; p[i][]-=x;
} kd[].len=kd[].len=;
kd[].num[]=kd[].num[]=;
for(int i=;i<=cnt;i++)
{
dealwith(prime[i]);
for(int t=;t<=;t++)
for(int j=;j<=p[prime[i]][t];j++)
kd[t]=kd[t]*pass;
} kd[].print(); printf(" ");
kd[].print(); printf("\n"); }
}
上一篇:mybatis-输出类型之resultMap


下一篇:Mybatis中查询返回多个对象使用resultType使用Map类型代替resultMap