【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 imes C_m^{c_1} imes C_{m-c_1}^{c_2} imes C_{m-c_1-c_2}^{c_3} ... over n^m$
最后取概率最大的n即可。这种方法在n更大，可能的取值更多的情况下也能用。
但是组合数太大了没法存，怎么办？取log即可。
注意如果10^7预处理阶乘会TLE。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <cmath>
using namespace std;
int m,tot,ans;
double mx,sum;
map<int,int> s;
int cnt[10010];
double jc[10010];
inline double c(int a,int b)
{
if(a<b) return -1e10;
return jc[a]-jc[a-b]-jc[b];
}
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+(gc^'0'),gc=getchar();
return ret*f;
}
int main()
{
m=rd();
register int n,i,a,tmp;
for(i=1;i<=m;i++)
{
a=rd();
if(!s[a]) s[a]=++tot;
cnt[s[a]]++;
}
mx=-1e10;
for(i=1;i<=m;i++) jc[i]=jc[i-1]+log(i);
for(n=10;n<=10000000;n*=10)
{
if(n<tot) continue;
sum=0;
for(i=1;i<=tot;i++) sum+=log(n-i+1)-log(i);
sum+=-log(n)*m,tmp=m;
for(i=1;i<=tot;i++) sum+=c(tmp,cnt[i]),tmp-=cnt[i];
if(sum>mx) mx=sum,ans=n;
}
printf("%d",ans);
return 0;
}