526互联

【SSL 2403】图床（三分）

发布时间 2023-03-31 10:42:58作者: あおいSakura

图床

题目链接：SSL 2403

题目大意

有 n 个物品，进行 m 次操作每次会随机选一个展示。
然后给你 n 个范围，要你猜测这个 n 的值。

思路

首先根据于假设一个 \(n\) 然后求实际可能的 \(n\) 值其实不行，因为你 \(n\) 可能很多。
不妨直接考虑一个 \(n\) 是的概率。

那全部的展示可能是 \(n^m\)。
考虑对应上它给你的展示。
注意到你无法直接判断 \(n\) 的原因是可能有一些从来没有展示过。
那你考虑 \(n\) 个物品最后展示了 \(k\) 个的概率，或者这里我们求方案除总数就是概率。

那考虑怎么算，首先我们选 \(k\) 个物品展示，那展示有展示的顺序（这里是第一次出现的顺序）。
那考虑先放下这些第一次出现的，然后考虑放别的。
那你放在第一次出现中第 \(i\) 个后面就有 \(i\) 中物品可以选，那按顺序放的话就接在直接后面或者你放过的后面都可以是一样的。
那总共就是 \(1+2+...+k\) 中地方*对应选法，那就是 \(k(k+1)/2\) 个方案每个数。
那总方案数就是 \(\binom{n}{k}k!(k(k+1)/2)^{m-k}=\dfrac{n!}{(n-k)!}(\dfrac{k(k+1)}{2})^{m-k}\)

那概率就是：
\(\dfrac{n!}{(n-k)!n^m}(\dfrac{k(k+1)}{2})^{m-k}\)

那我们要找的就是概率最大的那个。
那可以做到 \(O(T(n\max-n\min))\)，不过注意到很多东西都很大，不过只有乘法和除法，而且对精度的要求不高，可以把全部都转成指数加减，直接比较指数大小。

然后考虑到概率是数值，肯定是有偏序关系的，那考虑比较两个 \(n_1,n_2\) 的过程，假设 \(n_1\) 没有 \(n_2\) 优。
\(\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}\)
那注意到右边这一坨跟 \(n\) 压根没关系，可以直接不管。
\(\dfrac{n_1!}{(n_1-k)!n_1^m}<\dfrac{n_2!}{(n_2-k)!n_2^m}\)
\(n_1!(n_2-k)!n_2^m<n_2!(n_1-k)!n_1^m\)

那也就是我们只需要找到 \(\dfrac{n!}{(n-k)!n^m}\) 的最大值。
通过（猜结论 / 搞图像找规律 / 奇怪的数学证明），发现答案的这个东西是单峰的（当 \(\geqslant 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;
}