思路：

大神题。

考虑递归，我们令 $p = \operatorname{dfs}(w, now)$ 表示此时已知下标 $\ge now$ 的所有值时最多用 $w$ 的价钱可以知道下标 $\ge p$ 的值；初始使用 $\operatorname{dfs}(P_0 - 1, n)$。

对于一个 $\operatorname{dfs}(w, now)$ 来说，首先调用 $\operatorname{transaction}(w)$，得到一个购买子序列 $A$（设 $st = A_0$），此时显然可以得到这个子序列的价值之和 $sum$，考虑这个子序列的平均数 $-1$，显然此时不可能买到 $st$（这里 $-1$ 是为了防止 $|A| = 1$ 时再次买到）。

然后考虑子问题用 $\operatorname{dfs}(\frac{sum - 1}{|A|}, now)$ 去更新现在的 $now$，此时考虑 $A$ 后面所有大于等于 $now$ 的位置，用 $sum$ 减去其的贡献，重新找平均数 $-1$ 的价格进行调用递归，不断逼近，直到 $now \le st$。

显然最终会先递归到 $st$ 等于 $n - 1$ 的情况（因为当 $|A| = 1$ 且 $st$ 不等于 $n - 1$ 时会使用 $P_{st} - 1$ 的价格去买，继续往下）；同理，这会始终保证 $cnt_i \le i$，因为对于一个 $st$，其递归的下一个 $st$ 一定比它小，所以对于一个 $i$ 来说，只有 $st \le i$ 的 $st$ 可能会买到它，且每个 $i$ 只会作为一次 $st$。

最后你已经求出了 $P$，补全 $i - cnt_i$ 次 $P_i$ 即可。

完整代码：

#include <utility>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
std::pair<std::vector<int>, long long> transaction(long long M);
const int N = 105;
ll val[N];
int cnt[N];
inline int dfs(ll w, int now){
	auto t = transaction(w);
	auto A = t.fi;
	ll r = t.se;
	w -= r;
	for(auto v : A)
	  ++cnt[v];
	while(A.back() >= now){
		w -= val[A.back()];
		A.pop_back();
	}
	while(A.front() + 1 < now){
		now = dfs((w - 1) / A.size(), now);
		while(A.back() >= now){
			w -= val[A.back()];
			A.pop_back();
		}
	}
	val[A.front()] = w;
	return A.front();
}
void buy_souvenirs(int N, long long P0){
	dfs(P0 - 1, N);
	for(int i = 1; i < N; ++i){
		while(cnt[i] < i){
			++cnt[i];
			transaction(val[i]);
		}
	}
}

注意：这是在某交互大神帮助下完成的该题，并非独立做出。

秒赤，好玩。

很神秘的题意，交互但是目标不是得到某个值而是完成一个目标，第一次见。

我们先把交互库返回的东西处理一下，我们想要返回的几样商品的价值和，而不是剩下的钱。我们记返回值为 [a,b,c,...],x，方括号里的是商品集合，$x$ 是它们的价值和。

首先我们发现询问 $\ge P[0]$ 的值是不合法的，不然 $P[0]$ 就买了；过于小的值也是很危险的，毕竟你不知道 $P[n-1]$ 是什么，万一小于它你就买不到东西，也是不合法的。那么第一步我们能干什么？唯一安全的值应该是 $P[0]-1$。

知道了这个后，我们来手玩一下小数据，比如 $n=3$。

第一步问 $P[0]-1$，会有两种情况：

• 返回 [1] x。这下我们直接知道 $P[1]=x$，接着问一次 $P[1]-1$ 就能知道 $P[2]$ 了。
• 返回 [1,2] x。这该怎么办！1 号商品已经没有剩余购买次数了，下一步只能买一个 2。这意味着我必须找出一个 $x'\in[P[2],P[1])$ 来询问。容易发现 $x'=\lfloor\frac{x}{2}\rfloor$ 满足条件。

这下 $n=3$ 就解决了，拼盘 39pts 到手。

这个过程中，有几个点很有启发性：

1. 找出一个 $x'\in[P[2],P[1])$ 来询问：如果我们能够对每个 $i\in[1,n-1]$，都找到一个 $x\in [P[i],P[i-1])$ 询问一次，这样获得的信息会构成一组 $n-1$ 元线性方程组，而且是满秩的（因为这样一次询问，$i$ 商品一定会被买，且只有 $\ge i$ 的商品可能会被买，因此是对角线全为 1 的上三角），可以直接消元得到每一个 $P[i]$。而且如果对于每个 $[P[i],P[i-1])$ 恰好询问一次，一定能满足 $i$ 被买了 $\le i$ 次，不够的在解出 $P[i]$ 后补上即可。

2. $x'=\lfloor\frac{x}{2}\rfloor$ 满足条件：这提示我们使用上次询问的商品的平均价格来进行下次询问。因为这个平均一定会落在最大值和最小值之间，至少是安全的。

3. 知道 $P[i]$ 的值后，$x'=P[i]-1$ 一定属于 $[P[i+1],P[i])$，可以直接用。

有了这些前提后，我们定义一个求解函数 $f(S,x)$ ，其中 $S$ 是一个商品编号集，$x$ 是 $S$ 中商品的价值和（这个信息是由一次向交互库询问得来的）。这个函数做的事情是，求出 $\ge \min(S)$ 的所有商品的具体价值。

记 $\min(S)=m$，那么显然这个 $(S,x)$ 是上一次询问了一个 $x'\in[P[m],P[m-1])$ 得来的。为了满足每个 $[P[i],P[i-1])$ 恰好询问一次，我们需要保证 $m$ 只会作为 $\min(S)$ 出现一次。这个记忆化一下就好。

具体做法是：

1. 每次进入这个函数，所有已知商品价格的 $i$ 一定形成一段后缀（这个是函数本身的进行过程保证的）。我们不断检查 $\max(S)$ 的价格是否已经确定，如果是，就删除 $\max(S)$ 并相应的更新 $x$。（这一步其实是在消元）
2. （如果此时 $|S|>1$）基于启发点 (2)，求出剩余物品的平均价格 $avr=\lfloor\frac{x}{|S|}\rfloor$ 并进行一次询问。注意此时 $\min(S)$ 和 $\max(S)$ 之间的所有值我们应该都不知道，相应的所有 $[P[i+1],P[i])$ 也都没有被询问过，所以进行这个询问是合理的。询问完以后递归处理。
3. 重复 1，2 两步直到 $|S|=1$。此时容易发现 $\min(S)$ 应该仍然是 $m$，这个时候显然 $P[m]=x$。由启发点 (3)，此时我们获得了 $x-1\in[P[m+1],P[m])$，如果 $m+1$ 没有被处理过，那么询问一次 $x-1$ 并递归处理。

最开始询问一次 $P[0]-1$ 并调用即可。

最后显然可能有物品没买够的，既然我们已经求出所有物品的价格，询问 $P[i]$ 就能恰好买一个 $i$，补上即可。

最后补一句，容易发现这个 5000 次交互是假的。每次至少得买一个，总共最多买 $1+2+\dots+99=4950$ 次，根本不怕这个次数上限。