令序列中出现次数最多的数为 $x$，其他数的总个数为 $t$。则我们可以找出 $\min\{t,\lfloor\frac{n-k}{2}\rfloor\}$ 对数，使得每对中的两个数不同。我们重新排列所有数，使得一对数的位置相邻。考虑所有 $n-k+1$ 个前缀和，它们应当互不相同，否则就找到一个和为 $0$ 的子段。同时，如果我们交换一对数的位置，恰好一个前缀和会被改变，因此这总共 $n-k+1+\min\{t,\lfloor\frac{n-k}2\rfloor\}$ 个前缀和都应互不相同。因此 $t$ 必须小于 $k$。则 $x$ 出现的次数为 $n-k-t>n-2k\ge \frac n2$。因此 $x$ 必须与 $n$ 互素，它的方案数为 $\varphi(n)$。

接下来把所有数除掉 $x$，则序列中有大于 $\frac n2$ 个 $1$。所以其他数必须小于 $\frac n2$。进一步地，整个序列的和应当小于 $n$。这显然是充要条件，因此总方案数为 $\varphi(n)\cdot {n-1\choose k-1}$，可以在 $O(\sqrt n+k)$ 的时间内计算。