首页 > 代码库 > 【BZOJ2227】【ZJOI2011】看电影 [组合数学][质因数分解]
【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
1 1
2 1
2 2
Sample Output
0 1
3 4
HINT
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 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cstring> 5 #include<cstdlib> 6 #include<cmath> 7 using namespace std; 8 9 const int ONE=201; 10 11 int T; 12 int n,k; 13 int prime[ONE],cnt; 14 int p[ONE][3]; 15 int record,x; 16 17 struct power 18 { 19 int num[10001],len; 20 void print() 21 { 22 for(int i=len;i>=1;i--) 23 printf("%d",num[i]); 24 } 25 26 friend power operator *(power a,power b) 27 { 28 power c; 29 c.len=a.len+b.len; 30 for(int i=1;i<=c.len;i++) c.num[i]=0; 31 32 for(int i=1;i<=a.len;i++) 33 { 34 x=0; 35 for(int j=1;j<=b.len;j++) 36 { 37 c.num[i+j-1]=c.num[i+j-1] + x + a.num[i]*b.num[j]; 38 x=c.num[i+j-1]/10; 39 c.num[i+j-1]%=10; 40 } 41 c.num[i+b.len]=x; 42 } 43 44 while(c.len>1 && !c.num[c.len]) c.len--; 45 return c; 46 } 47 }kd[3],pass; 48 49 void dealwith(int x) 50 { 51 for(int i=1;i<=pass.len;i++) pass.num[i]=0; 52 pass.len=0; 53 while(x) 54 { 55 pass.num[++pass.len]=x%10; 56 x/=10; 57 } 58 } 59 60 int get() 61 { 62 int res=1,Q=1;char c; 63 while( (c=getchar())<48 || c>57 ) 64 if(c==‘-‘)Q=-1; 65 res=c-48; 66 while( (c=getchar())>=48 && c<=57 ) 67 res=res*10+c-48; 68 return res*Q; 69 } 70 71 int PD(int x) 72 { 73 for(int i=2;i<x;i++) 74 if(x%i==0) return 0; 75 return 1; 76 } 77 78 int Chai(int x,int PD) 79 { 80 if(x==1) return x; 81 for(int i=1;i<=cnt;i++) 82 { 83 if(!(x%prime[i])) 84 { 85 p[prime[i]][PD]++; 86 x=Chai(x/prime[i],PD); 87 break; 88 } 89 } 90 return x; 91 } 92 93 int Deal(int x,int m,int PD) 94 { 95 record=1; 96 for(int i=1;i<=m;i++) 97 { 98 record*=x; 99 record=Chai(record,PD);100 }101 102 if(PD==1)103 {104 record*=(x-m-1);105 record=Chai(record,PD);106 }107 108 p[record][PD]++;109 }110 111 int main()112 {113 T=get();114 for(int i=2;i<=200;i++)115 if(PD(i)) prime[++cnt]=i;116 117 while(T--)118 {119 n=get(); k=get();120 if(n>k)121 {122 printf("0 1\n");123 continue;124 }125 126 memset(p,0,sizeof(p));127 Deal(k+1,n-1,1); Deal(k,n,2);128 for(int i=1;i<=200;i++)129 {130 int x=min(p[i][1],p[i][2]);131 p[i][1]-=x; p[i][2]-=x;132 }133 134 kd[1].len=kd[2].len=1;135 kd[1].num[1]=kd[2].num[1]=1;136 for(int i=1;i<=cnt;i++)137 {138 dealwith(prime[i]);139 for(int t=1;t<=2;t++)140 for(int j=1;j<=p[prime[i]][t];j++)141 kd[t]=kd[t]*pass;142 }143 144 kd[1].print(); printf(" ");145 kd[2].print(); printf("\n");146 147 }148 }
【BZOJ2227】【ZJOI2011】看电影 [组合数学][质因数分解]