又掌握一种递归题型

看到这个题，首先想到了约瑟夫环，这不就是一个变种的约瑟夫环吗，但n的最大值为$10^9$，显然使用数组和队列解决约瑟夫环的方法，因为超存储和超时在这里无法使用。又想到曾做过一道约瑟夫环问题：A101157.约瑟夫问题，使用跳变的方式加速找到元素，貌似可以规避掉超存储和超时间的问题，但这个方法最后只做到了得到剩余的元素数量，而无法获知剩余元素的原始编号，而如果要对应起来，显然又涉及到存储问题。

这里开始思考：如何可以从最后的剩余元素个数推出这些元素的原始编号。重复操作的停止条件是剩余凋零骷髅的个数不足4只；而从这不足4只再回推原始编号。哈，灵光乍现——递进+回归——递归。

傻子一个，本来就是在做递归专题的题目呀，不是递归是什么。

递进过程很好想到：只要大于等于4个，就重复操作：四个组队走，剩一个；不够组队都剩下
回归过程：回归要从返回的结果推出现在的编号，而推现在的编号需要知道有几个完整的队以及非完整队的元素个数。

具体代码实现如下，代码中也有注释，应该还是比较好理解的。

#include<bits/stdc++.h>
using namespace std;
//递归函数：返回当有 n 只洞灵骷髅时，最终剩下的骷髅的原始编号
vector<int> getRem(int n) {
	//终止条件：不足 4 只，无法分组，全部留下
	if(n<=3) {
		vector<int> ans;
		for(int i=0; i<n; ++i) ans.push_back(i+1); //编号为 1, 2, ..., n
		return ans;
	}
	//计算这一轮结束后剩下多少只
	int groups = n/5;  //完整组数
	int rem = n%5; //不完整组的元素个数
	int next_n = groups + (rem<4?rem:0);  //下一次操作的元素个数
	//递归获取下一轮剩下的骷髅在下一轮中的新编号
	vector<int> pos = getRem(next_n);
	//反向映射：将下一轮的新编号映射回当前轮的原始编号
	vector<int> cur_pos;
	for(int p : pos) {
		if(p <= groups) {
			cur_pos.push_back(5*p); //第p个完整组中的第5个，编号：p->5p
		} else {
			// 属于最后不足 4 个的部分，映射编号：p->5*groups+(p-groups)
			cur_pos.push_back(5*groups+(p-groups));
		}
	}
	return cur_pos;
}
int main() {
	int n;
	cin>>n;
	vector<int> ans=getRem(n);
	cout<<ans.size()<<endl;   //输出最终剩下的凋灵骷髅数量
	for (int &x : ans) cout<<x<<" ";  //从小到大输出最终留下的凋灵骷髅编号
	return 0;
}