【BZOJ5094】硬盘检测
Description
很久很久以前,小Q买了一个大小为n单元的硬盘,并往里随机写入了n个32位无符号整数。因为时间过去太久,硬盘上的容量字眼早已模糊不清,小Q也早已忘记了硬盘的容量。小Q记得,n可以被表示成10^k(1<=k<=7)的形式,即十到一千万。他还记得自己曾经m次随机读取某个32位无符号整数的记录。小Q现在正在Quapler宇宙飞船上遨游WF18星座,所以他想请你帮他找出n的具体大小。
Input
第一行包含一个正整数m(m=10000),表示随机访问硬盘的次数。
接下来m行,每行一个整数a_i(0<=a_i<2^{32}),即每次随机访问读取的结果。
Output
输出一行一个整数,即n的大小。
题解:难道只有我把具体的概率算出来了吗。。。好多人都是分析数据+特判过的。
我们可以直接算出对于n的所有取值,出现给定情况的概率是多少。如果m个数中本质不同的有k个,每个出现的次数为c1,c2...ck,于是这种情况的概率就是:
$C_n^k\times C_m^{c_1}\times C_{m-c_1}^{c_2}\times C_{m-c_1-c_2}^{c_3} ... \over n^m$
最后取概率最大的n即可。这种方法在n更大,可能的取值更多的情况下也能用。
但是组合数太大了没法存,怎么办?取log即可。
注意如果10^7预处理阶乘会TLE。
#include#include #include #include