图床
题目链接：SSL 2403
题目大意
有 n 个物品，进行 m 次操作每次会随机选一个展示。
然后给你 n 个范围，要你猜测这个 n 的值。
思路
首先根据于假设一个
n
n
n 然后求实际可能的
n
n
n 值其实不行，因为你
n
n
n 可能很多。
不妨直接考虑一个
n
n
n 是的概率。
那全部的展示可能是
n
m
n^m
nm。
考虑对应上它给你的展示。
注意到你无法直接判断
n
n
n 的原因是可能有一些从来没有展示过。
那你考虑
n
n
n 个物品最后展示了
k
k
k 个的概率，或者这里我们求方案除总数就是概率。
那考虑怎么算，首先我们选
k
k
k 个物品展示，那展示有展示的顺序（这里是第一次出现的顺序）。
那考虑先放下这些第一次出现的，然后考虑放别的。
那你放在第一次出现中第
i
i
i 个后面就有
i
i
i 中物品可以选，那按顺序放的话就接在直接后面或者你放过的后面都可以是一样的。
那总共就是
1
+
2
+
.
.
.
+
k
1+2+...+k
1+2+...+k 中地方*对应选法，那就是
k
(
k
+
1
)
/
2
k(k+1)/2
k(k+1)/2 个方案每个数。
那总方案数就是
(
n
k
)
k
!
(
k
(
k
+
1
)
/
2
)
m
−
k
=
n
!
(
n
−
k
)
!
(
k
(
k
+
1
)
2
)
m
−
k
\binom{n}{k}k!(k(k+1)/2)^{m-k}=\dfrac{n!}{(n-k)!}(\dfrac{k(k+1)}{2})^{m-k}
(kn)k!(k(k+1)/2)m−k=(n−k)!n!(2k(k+1))m−k
那概率就是：
n
!
(
n
−
k
)
!
n
m
(
k
(
k
+
1
)
2
)
m
−
k
\dfrac{n!}{(n-k)!n^m}(\dfrac{k(k+1)}{2})^{m-k}
(n−k)!nmn!(2k(k+1))m−k
那我们要找的就是概率最大的那个。
那可以做到
O
(
T
(
n
max
−
n
min
)
)
O(T(n\max-n\min))
O(T(nmax−nmin))，不过注意到很多东西都很大，不过只有乘法和除法，而且对精度的要求不高，可以把全部都转成指数加减，直接比较指数大小。
然后考虑到概率是数值，肯定是有偏序关系的，那考虑比较两个
n
1
,
n
2
n_1,n_2
n1,n2 的过程，假设
n
1
n_1
n1 没有
n
2
n_2
n2 优。
n
1
!
(
n
1
−
k
)
!
n
1
m
(
k
(
k
+
1
)
2
)
m
−
k
<
n
2
!
(
n
2
−
k
)
!
n
2
m
(
k
(
k
+
1
)
2
)
m
−
k
\dfrac{n_1!}{(n_1-k)!n_1^m}(\dfrac{k(k+1)}{2})^{m-k}<\dfrac{n_2!}{(n_2-k)!n_2^m}(\dfrac{k(k+1)}{2})^{m-k}
(n1−k)!n1mn1!(2k(k+1))m−k<(n2−k)!n2mn2!(2k(k+1))m−k
那注意到右边这一坨跟
n
n
n 压根没关系，可以直接不管。
n
1
!
(
n
1
−
k
)
!
n
1
m
<
n
2
!
(
n
2
−
k
)
!
n
2
m
\dfrac{n_1!}{(n_1-k)!n_1^m}<\dfrac{n_2!}{(n_2-k)!n_2^m}
(n1−k)!n1mn1!<(n2−k)!n2mn2!
n
1
!
(
n
2
−
k
)
!
n
2
m
<
n
2
!
(
n
1
−
k
)
!
n
1
m
n_1!(n_2-k)!n_2^m<n_2!(n_1-k)!n_1^m
n1!(n2−k)!n2m<n2!(n1−k)!n1m
那也就是我们只需要找到
n
!
(
n
−
k
)
!
n
m
\dfrac{n!}{(n-k)!n^m}
(n−k)!nmn! 的最大值。
通过（猜结论 / 搞图像找规律 / 奇怪的数学证明），发现答案的这个东西是单峰的（当
⩾
k
\geqslant k
⩾k 的时候）。（不想证了搞数学式子搞麻了）
然后三分即可。
代码
#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>
#define ll long long
#define ull unsigned long long
using namespace std;
const int Size=1<<23,NN=1e5+5,M=65535;
char buf[Size],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,Size,stdin),p1==p2)?EOF:*p1++)
int re; char c;
int read() {
re = 0; c = getchar();
while (c < '0' || c > '9') c = getchar();
while (c >= '0' && c <= '9') {
re = (re << 3) + (re << 1) + c - '0';
c = getchar();
}
return re;
}
void readd() {
c = getchar();
while (c < '0' || c > '9') c = getchar();
while (c >= '0' && c <= '9') c = getchar();
if (c == '.') {
c = getchar();
while (c >= '0' && c <= '9') c = getchar();
}
}
const int P = 1e5 + 1000;
int nmin, nmax, m, cnt;
ull a[P];
double jc[P], log2_[P];
bool f(int x, int y) {
return jc[x] + jc[y - cnt] + log2_[y] * m < jc[y] + jc[x - cnt] + log2_[x] * m;
}
int main() {
freopen("pic.in", "r", stdin);
freopen("pic.out", "w", stdout);
for (int i = 1; i < P; i++) {
log2_[i] = log10(i) / log10(2);
jc[i] = jc[i - 1] + log2_[i];
}
int T = read(); readd(); readd(); readd(); readd(); nmin = read(); nmax = read(); m = read();
while (T--) {
for (int i = 1; i <= m; i++) {
c = getchar(); while (c < 'a' || c > 'z') c = getchar();
ull now = 0;
while (c >= 'a' && c <= 'z') {
now = now * 26 + c - 'a';
c = getchar();
}
a[i] = now;
}
sort(a + 1, a + m + 1);
cnt = 1;
for (int i = 2; i <= m; i++)
if (a[i] != a[i - 1]) cnt++;
int L = max(cnt, nmin), R = nmax;
while (R - L + 1 >= 2) {
int mid = (L + R) >> 1;
if (f(mid, mid + 1)) L = mid + 1;
else R = mid;
}
int re = L;
for (int i = L; i < R; i++) if (f(re, i + 1)) re = i + 1;
printf("%d\n", re);
}
return 0;
}