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

2023-10-08 10:59

本文主要是介绍【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

  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 }
View Code

 

转载于:https://www.cnblogs.com/BearChild/p/6440501.html

这篇关于【BZOJ2227】【ZJOI2011】看电影 [组合数][质因数分解]的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/164791

相关文章

hdu4869(逆元+求组合数)

//输入n,m,n表示翻牌的次数,m表示牌的数目,求经过n次操作后共有几种状态#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#includ

Python:豆瓣电影商业数据分析-爬取全数据【附带爬虫豆瓣,数据处理过程,数据分析,可视化,以及完整PPT报告】

**爬取豆瓣电影信息,分析近年电影行业的发展情况** 本文是完整的数据分析展现,代码有完整版,包含豆瓣电影爬取的具体方式【附带爬虫豆瓣,数据处理过程,数据分析,可视化,以及完整PPT报告】   最近MBA在学习《商业数据分析》,大实训作业给了数据要进行数据分析,所以先拿豆瓣电影练练手,网络上爬取豆瓣电影TOP250较多,但对于豆瓣电影全数据的爬取教程很少,所以我自己做一版。 目

Go组合

摘要 golang并非完全面向对象的程序语言,为了实现面向对象的继承这一神奇的功能,golang允许struct间使用匿名引入的方式实现对象属性方法的组合 组合使用注意项 使用匿名引入的方式来组合其他struct 默认优先调用外层方法 可以指定匿名struct以调用内层方法 代码 package mainimport ("fmt")type People struct{}type Pe

组合c(m,n)的计算方法

问题:求解组合数C(n,m),即从n个相同物品中取出m个的方案数,由于结果可能非常大,对结果模10007即可。       共四种方案。ps:注意使用限制。 方案1: 暴力求解,C(n,m)=n*(n-1)*...*(n-m+1)/m!,n<=15 ; int Combination(int n, int m) { const int M = 10007; int

代码随想录训练营day37|52. 携带研究材料,518.零钱兑换II,377. 组合总和 Ⅳ,70. 爬楼梯

52. 携带研究材料 这是一个完全背包问题,就是每个物品可以无限放。 在一维滚动数组的时候规定了遍历顺序是要从后往前的,就是因为不能多次放物体。 所以这里能多次放物体只需要把遍历顺序改改就好了 # include<iostream># include<vector>using namespace std;int main(){int n,m;cin>>n>>m;std::vector<i

INDEX+SMALL+IF+ROW函数组合使用解…

很多人在Excel中用函数公式做查询的时候,都必然会遇到的一个大问题,那就是一对多的查找/查询公式应该怎么写?大多数人都是从VLOOKUP、INDEX+MATCH中入门的,纵然你把全部的多条件查找方法都学会了而且运用娴熟,如VLOOKUP和&、SUMPRODUCT、LOOKUP(1,0/....,但仍然只能对这种一对多的查询望洋兴叹。   这里讲的INDEX+SMALL+IF+ROW的函数组合,

代码随想录算法训练营Day37|完全背包问题、518.零钱兑换II、377. 组合总和 Ⅳ、70. 爬楼梯(进阶版)

完全背包问题                  和01背包最大区别就是一个物品可以重复放多次,因此遍历空间时可以从前往后。 import java.util.*;public class Main{public static void main (String[] args) {Scanner sc = new Scanner(System.in);int m = sc.nextInt

【内网】ICMP出网ew+pingtunnel组合建立socks5隧道

❤️博客主页: iknow181 🔥系列专栏: 网络安全、 Python、JavaSE、JavaWeb、CCNP 🎉欢迎大家点赞👍收藏⭐评论✍ 通过环境搭建,满足以下条件: 攻击机模拟公网vps地址,WEB边界服务器(Windows Server 2008)模拟公司对外提供Web服务的机器,该机器可以通内网,同时向公网提供服务。内网同网段存在一台Windows内网服务

数据预处理与协同过滤推荐算法——从数据清洗到个性化电影推荐

推荐系统在现代应用中占据了重要地位,尤其在电影、音乐等个性化内容推荐中广泛使用。本文将介绍如何使用数据预处理、特征工程以及多种推荐算法(包括协同过滤、基于内容的推荐、混合推荐等)来实现电影推荐系统。通过Pandas、Scikit-learn、TensorFlow等工具,我们将展示如何从数据清洗开始,逐步实现各类推荐算法。  完整项目代码: 基于协同过滤的电影推荐系统 一、数据预处

下一代皮克斯:AI如何融合电影与游戏

故事是人类体验的核心,通过故事我们理解世界、寻找意义并与他人建立联系。技术的进步不断推动着故事叙述的形式,从迪士尼的多平面摄影机到皮克斯的3D图形技术,每一次技术革命都带来了故事叙述的新方式。 游戏:现代叙事的前沿 今天,有两个主要的趋势正在加速下一代叙事公司的诞生: 消费者转向互动媒体:过去三十年间,我们见证了消费者从传统的线性媒体(如电视和电影)向互动媒体(如游戏)的逐步迁移。对于Z世