故且也算是两种特殊的dp问题？感觉一般也就是应用在一些板子题上（

约瑟夫问题

有 \(n\) 个人排成一个环，从 \(0\) 到 \(n - 1\) 编号，从 \(0\) 开始报数，每数到 \(k\) 就枪毙一个人，问最后剩的人的编号。

法一：

嗯暴力 \(+\) 队列直接扫过去。

法二：

一个 \(O(n)\) 的 \(dp\)。

设 \(f(n,k)\) 为初始 \(n\) 个人时，数 \(k\) 个人就枪毙一下的约瑟夫问题的答案，那么有如下的 \(dp\) 方程：

思路比较简单，考虑枪毙一个人后人数就变成了 \(n-1\)，并且从枪毙的这个人开始又数 \(k\) 个人再枪毙，即位置下标加 \(k\)，并且又是一个环，模 \(n\) 即可。时间复杂度为 \(O(n)\)。

法三

第二种方法对于 \(n\) 很大，但 \(k\) 很小的情况就显得有些疲软了。不妨考虑这样一个问题：我们一遍扫过所有人后，是否可以一次性毙 \(n / k\) 个人，并计算出毙了这些人后的下一个位置的下标呢？
不妨模拟一下。假设 \(n\) 为 \(8\)，\(k\) 为 \(3\)。

先扫一遍过去，存活人数变为 \(n - n/k=6\) 人，情况如下（打 \(x\) 的表示被枪毙的）：

重编号一下，使下一轮开始的编号从 \(0\) 开始。

最后一个 \(X\) 的下标为 \(n - n \mod k\)。

假设现在形成的这样一个 \(f(n - n / k,k)\) 规模的约瑟夫问题的答案在最后一个 \(X\) 后面，即 \(f(n - n / k,k) < n \mod k\)，就相当于整个过程中，答案的变化是单增的，我们只需将 \(f(n - n / k,k)\) 的答案加上最后一个 \(X\) 的下标即可，这种情况的答案就是：

假设这个 \(f(n - n / k,k)\) 规模的约瑟夫问题的答案在最后一个 \(X\) 的位置之前呢？
那就相当于是在最后一个 \(X\) 前删人，每删一个人，后面的人依次继承前一个人的编号，就不存在刚刚那种重编号后后面的人的编号反而比前面小的情况了。

减去 \(n \mod k\) 表示消除 \(X\) 后面那撮人对答案的影响。又为什么要乘一个 \(k / (k - 1)\) 呢？

因为每数 \(k\) 个人就要枪毙一下，因此每 \(k - 1\) 个人分一组，每组最后一个人的下一个人在这一轮中会被枪毙。因此先除以一个 \((k-1)\)，得到答案在当前所属分组的编号。再乘 \(k\)，就把答案调到了正确的位置。

不过这样就极大地降低了时间复杂度，达到了 \(O(klogn)\)。

贴个代码先：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1e5;
int nn,kk;
int s(int n, int k){
  if (n == 1) return 0;//还剩一个人时，重编号后能唯一确定剩下的人的编号为 0
  if (k == 1) return n - 1;
  if (k > n) return (s(n - 1, k) + k) % n;//如果 k 大于 n，那么就O(n)做
  int res = s(n - n / k, k);
  res -= n % k;
  if (res < 0)//如果答案在最后一个X后
    res += n;//恢复到正常下标
  else
    res += res / (k - 1);//如上文所说
  return res;
}

signed main(){
    scanf("%lld%lld",&nn,&kk);
    int a = s(nn,kk);
    cout << a + 1;
}

* 扩展：

求第 \(k\) 个被枪毙的人的编号

显然也可以 \(O(n)\) \(dp\)，控制一下转移次数即可。

还有一种 \(O(klogn)\) 的做法，基本思想就是从当前报数的编号推上一次报数的编号，思路如下：

设第 \(p\) 次报数的人是 \(y\)，令 \(p = a * m + b,b < m\)。
经过前 \(p\) 次报数，一共有 \(a\) 个人失去了他宝贵的生命，还剩 \(n-a\) 人。
假如 \(y\) 没有在这一次报数中被淘汰，那么他下一次报数的编号就是 $$q = p + n - a = n + (m - 1) * a + b$$
即可推 \(a = \frac{q - b - n}{m - 1}\)，有因为 \(b < m\)，则 \(a = \frac{q - n}{m -1}\)。
然而 \(p = q - n + a = q - n + \frac{q - n}{m - 1}\)，这是由这一次报数推上一次报数的计算式。

然后要求第 \(k * m - 1\) 报数的人的编号是多少，用这个式子嗯推就行了。

int kth(int n,int m,int k){
	if(m == 1)return n - 1;
	for(k = k * m + m - 1; k >= n; k = k - n + (k - n) / (m - 1));//因为k，n都是从0开始计数的，所以从 k * m + m - 1开始
	return k；
}

扔鸡蛋问题：

\(n\) 层楼，从 \(m\) 层扔鸡蛋下去会砸碎。有 \(k\) 个鸡蛋，问为了找出这个 \(m\) 最少需要实验多少次。

法一

定义状态 \(f(i,j)\) 为 \(i\) 层楼，\(j\) 个鸡蛋最少需要实验多少次。
假设从 \(x\) 楼扔了个鸡蛋下去，这玩意儿碎了，那么 \(f(i,j) = f(x - 1,j - 1) + 1\)。
如果没碎，则 \(f(i,j) = f(i - x,j) + 1\)。
综上，式子为：

复杂度为 \(O(n^2k)\)，似乎不太优。

法二

考虑换一种状态定义：\(f(i,j)\) 表示实验 \(i\) 次，\(j\) 个鸡蛋最多能够探测多少层楼。

求出来后二分求答案即可。

#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int MAXN = 1e3;
const int INF = 10000000000000000;
int T,n,k,dp[MAXN + 5][1005];
bool check(int x){
	if(x <= MAXN)return dp[x][k] >= n;
	int now = x,s = x;
	for(int i = 2; i <= k; i++){
		if(now * (long double)(x - i + 1) / i >= 1e18)return 1;
		now = now * (x - i + 1) / i;
		s = s + now;
		if(s >= n)return 1;
	}
	return s >= n;
}	
signed main(){
	for(int i = 1; i <= MAXN; i++){
		for(int j = 1; j <= 1000; j++){
			dp[i][j] = min(INF,1 + dp[i - 1][j] + dp[i - 1][j - 1]);
		} 
	}
	scanf("%lld",&T);
	while(T--){
		int cntt;
		scanf("%lld%lld%lld",&cntt,&k,&n);
		int l = 0,r = n - 1;
		r = INF - 1;
		while(l + 1 < r){
			int mid = (l + r) / 2;
			if(check(mid))r = mid;
			else l = mid;
		}
		cout << cntt << " " << r << "\n";;
	}
}