自动搬运

查看原文

来自洛谷，原作者为

	max0810 刚刚上初一，正在学习数据结构，求大佬带

搬运于2025-08-24 22:54:58，当前版本为作者最后更新于2024-02-06 11:09:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

我们首先观察到，对于 popcount 相同的数，它们的答案是一样的。设一个数的二进制中有 $n$ 个 $1$，那这个数下一步就可以走到 $n$ 个不同的 popcount 为 $n-1$ 的数。

由于终点是不固定的，那么以一个 popcount 为 $n$ 的数为起点的路径一共有 $n+n(n-1)+n(n-1)(n-2)+\ldots+n(n-1)\times\ldots\times 2$ 条（$0$ 不能当作终点），也就是 $\sum_{i=1}^{n-1}\frac{n!}{i!}$。

所以我们可以枚举 popcount 是多少：

$$\begin{aligned} \sum_{i=1}^{2^n}\sum_{j=1}^{2^n}f_{i,j} &= \sum_{i=1}^n \binom n i\sum_{j=1}^{i-1}\frac{i!}{j!} \\ &= \sum_{i=1}^n \frac{n!}{i!(n-i)!}\sum_{j=1}^{i-1}\frac{i!}{j!} \\ &= \sum_{i=1}^n \frac{n!}{(n-i)!}\sum_{j=1}^{i-1}\frac 1 {j!} \end{aligned} $$

令 $f(n) = \sum_{i=1}^n \frac 1 {i!}$，然后我们改变枚举方式，用 $n-i$ 来代替 $i$：

$$\sum_{i=1}^n \frac{n!}{(n-i)!}\sum_{j=1}^{i-1}\frac 1 {j!} = \sum_{i=0}^{n-1} \frac{n!}{i!}\times f(n-i-1) $$

然后我们考虑怎么优化时间复杂度，这里可以用递推的方式。具体地，我们令 $ans_n$ 表示 $n$ 的答案，则：

$$\begin{aligned} ans_{n+1}-ans_n &= \frac{(n+1)!}{n!}\times f(n+1-n-1)+\sum_{i=0}^{n-1}(\frac{(n+1)!}{i!}\times f(n-i)-\frac{n!}{i!}\times f(n-i-1)) \\ &= \sum_{i=0}^{n-1}\frac{(n+1)!\times f(n-i)-n!\times f(n-i-1)}{i!} \\ &= \sum_{i=0}^{n-1}\frac{(n+1)!\times(\frac 1 {(n-i)!}+f(n-i-1))-n!\times f(n-i-1)}{i!} \\ &= \sum_{i=0}^{n-1}\frac{((n+1)!-n!)\times f(n-i-1)}{i!}+\sum_{i=0}^{n-1}\frac{(n+1)!}{(n-i)!i!} \\ &= \sum_{i=0}^{n-1}\frac{n\times n!\times f(n-i-1)}{i!}+\sum_{i=0}^{n-1}(n+1)\binom{n}{i} \\ &= n\times ans_{n}+(n+1)(2^n-1) \\ ans_{n+1} &= (n+1)ans_n+(n+1)(2^n-1) = (n+1)(ans_n+2^n-1) \end{aligned} $$

所以递推公式就是：

$$ans_n = n(ans_{n-1}+2^{n-1}-1)$$

代码：

int main()
{
    int t = rd();
    for(int i = 1;i < N;i++,p = p*2%mod)
        f[i] = i*(f[i-1]+p-1)%mod;
    while(t--)printf("%lld\n",f[rd()]);
    return 0;
}