题解 CF1242D 【Number Discovery】
CYJian
2020-03-26 19:15:49
毒瘤结论题...
先考虑，将 $s$ 数列中的每个数分成两类：
1. 被选出的 $k$ 个数求和加入 $s$ 数列的数。
2. 被从小到大选择加入 $s$ 数列的数。
然后，就有一个牛逼结论：
从 $1$ 开始，每 $k^2+1$ 个数分一个段，即第 $i$ 段包含的数是 $[(k^2+1) \times i+1,(k^2+1) \times(i+1)]$（这里认为 $i$ 从 $0$ 开始），则有，每段中有且仅有一个数，是属于第一类数。
然后考虑证明：
首先，对于 $i=0$，不难发现，其中有且仅有一个第一类数，它的值是 $\frac{k(k+1)}{2}$。
然后考虑计算后面的第一类数。我们如果知道第 $i$ 段的第一类数是 $x$，则可以知道第 $i \times k \sim (i + 1) \times k - 1$ 段中第一类数是啥。
考虑如何求出第 $i \times k + t + 1$ 段中第一类数是谁。
根据题意，我们有：
$$ \sum_{j=1}^{k}(i \times (k^2+1)+t\times k+j + [i \times (k^2+1)+t\times k+j \leq x]) $$
大概化简一下柿子，就有：
$$ (i \times k+t) \times (k^2+1)+\frac{k(k+1)}{2} - t + \max(0, \min(k, i \times (k^2+1)+(t+1)\times k-x+1))$$
然后注意到，$\frac{k(k+1)}{2}-t + \max(0, \min(k, i \times (k^2+1)+(t+1)\times k-x+1)) \in [1,k^2+1]$，所以这个数一定在第 $i \times k + t + 1$ 段中，所以一开始的那个结论也就成立了。
当然，有了这个结论以及这个柿子之后，这个题就能做了：
考虑一次询问 $n$ 和 $k$，我们先算出 $n$ 是在第 $\left\lfloor\frac{n-1}{k^2+1}\right\rfloor$ 段中。然后我们可以用倍增求出这个段中的第一类数是 $V$。如果 $n = V$，则可以直接求出，这个数是在序列中的第 $(\left\lfloor\frac{n-1}{k^2+1}\right\rfloor+1) \times (k+1)$ 项上。
如果 $n \ne V$，则考虑求出 $n$ 前面出现了多少大于它的第一类数。不难发现，由 $n$ 前面的数一共能在 $s$ 中生成 $\left\lfloor\frac{n-1}{k^2+1}\right\rfloor \times k + \frac{((n-1)\bmod(k^2+1))-[n \ge V]}{k}$ 个第一类数。而小于 $n$ 的第一类数共有 $\left\lfloor\frac{n-1}{k^2+1}\right\rfloor + 1 - [n < V]$ 种，然后加减一下就得到 $n$ 所在的位置了。
然后倍增的时候，直接按照上面化简的柿子递归计算就行了。
看起来柿子很恐怖，事实上非常好写。
$\rm Code$：
```cpp
inline ll S(ll x, ll k) { return (x + x + k - 1) * k / 2; }
inline ll find(ll x, ll k) {
if(!x) return k * (k + 1) >> 1;
ll p = find(x / k, k), rest = x % k;
ll st = (x / k) * (k * k + 1) + rest * k + 1;
if(st + k <= p) return S(st, k);
else return S(st, k) + min(k, st + k - p);
}
inline void Solve() {
ll n = rl, k = ri, bel = (n - 1) / (k * k + 1);
ll p = find(bel, k);
if(p == n) cout << (bel + 1) * (k + 1) << endl;
else {
ll pos = n - bel - 1 + (n < p);
ll t = (n - 1) % (k * k + 1) + 1;
ll cnt = bel * k + (t - 1 - (n >= p)) / k;
cout << pos + cnt << endl;
}
}
int main() {
int Case = ri;
while(Case--) Solve();
return 0;
}
```