占座位
君のNOIP。
2020-09-19 20:20:39
先特判 $k=0 $ 时显然能坐满所有座位。
设 $f_n$ 为 $n$ 个座位能坐的人数。
当 $1\le n <2 \times k + 2 $ 时，显然只能坐 $1$ 个人。
当 $n\ge 2\times k + 2 $ 时，设第 $2$ 个人坐到 $x$ 号座位，可以想象将 $1$ 和 $x$ 号座位移到一起，发现座位被分成左右两部分，按照这个方式递归求解即可。
$f(n)=\begin{cases}1&1\le n <2 \times k + 2 \\
f(\left\lfloor\dfrac{n}{2}\right\rfloor) + f(n-\left\lfloor\dfrac{n}{2}\right\rfloor)&n \ge 2 \times k + 2\end{cases}$
但这样当 $x$ 为奇数时 $f(x)$ 就会递归到两个子函数去，实际上这样会导致很多次重复计算，所以当 $n=10^{18}$ 时会 $\text{TLE}$。
可以发现过程中最多只会递归到 $2\times log_2^n$ 个数，所以记忆化搜索。
最简单的做法是用 $\text{map}$ 记录 $f_x$。
要是真不会用 $\text{map}$ 的话，反正递归到的数还不到 $120$ 个，用数组暴力排序应该也能过。
### Code：
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
using namespace std;
#define LL long long
map<LL,LL>mp;
LL n, k;
LL f( LL x ) {
if( x < 2 * k + 2 ) return 1;
if(mp[x]) return mp[x];
return mp[x] = f(x/2) + f(x-x/2);
}
int main() {
cin >> n >> k;
if( !k ) {
cout << n;
return 0;
}
cout << f(n);
}
```