包含所有各项不大于n的n元正整数列且长度最小的序列有多少个？ 第1页

最少长度是 ，用类似于贪心法的思想即可构造（已有答主构造）。

猜测最佳序列的个数是 。这里证明最佳序列个数的上界是 ，并给出探索下界的方法。

有一个上界

以 为例。考虑长度为 的串 。以 为结尾的串有 个： 。对于这三个中的任一个，如果它在最佳序列中，那么它接下去的串一定要以 打头。而以 打头的串也有 个 。现在要把 分配到 后面，有 种分配方案。

（比如题目的例子 关于串 的分配方案是 ）

但是假如考虑长度为 的串 ，此时就要把 分配到 后面。注意到 不能接在 后面，因此会少 种情况，只有 种分配方案。

长度为 的串共有这些： ，其中前 个只有 种分配方案，后 个有 种分配方案，因此搭配起来共有 种分配方案。

在同一种分配方案中，可以指定任一串作为开头。选好开头以后，再配上分配方案，就唯一确定了整个序列了。由于一共有 个长度为 的串，因此有 个开头方式。这样一共就有 个可能的序列。当然这些序列并不都是满足题意的序列，因此只是一个上界估计。从题中可以看到这是真实数据的 倍。

一般而言，固定长度为 的串 （ ），以这 位为末尾的串一共有 个（记为 ）。

显见，如果最佳方案中 后接一个数，则下一个串必须以 打头。而以 打头的串也是只有 个（记为 ）。现在要将 分配到 后面。

假如 中 中不全相等（这样的串有 个），那么 是互不相同的 个数，因此将 分配到 后面有 种分配方案；否则若 （这样的串有 个），那么存在且仅存在一对 使得 ，此时将 分配到 后面有 种分配方案（因为 不能放到 后面）。因此，搭配起来总共的分配方案数是

每种分配方案可以选定 个开头，给定开头和分配方案后就唯一确定了整个序列，因此所有序列的个数的上界就是

下界的思路

我的想法是局部替换。比如题目中的例子 ，按刚才 的例子，其实就是这么分配的

， ， （虽然 在末尾，但是如果首尾相接的话你会看到 ）

现在我想生成其他分配方案。比如生成 。那么我局部替换一下，比如现在让 ，那么直接定位到 ，其后的部分直到 之前是 ，现在再让 ，那么定位到 ，其后的部分直到 之前是 。最后让 。因此这样粘合就得到了

按照这种局部替换方法，就可以生成其他分配方案。