自动搬运

查看原文

来自洛谷，原作者为

	Jelefy 悲惨退役选手

搬运于2025-08-24 21:32:10，当前版本为作者最后更新于2020-02-03 01:39:37，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

鄙人证明此题的方法。

计算$n$排列的答案时，考虑在$(n-1)$排列的末尾加入一个$1\sim n$之间的数$x$（前面$n-1$个数中若有$≥x$的数默认$+1$）。
显然当$x$分别取不同值时，方案数是相等的【即$(n-1)!$】。
当新加入的数$x∈[1,n-1]$时，答案不变，只有当$x=n$时，才会在原来的基础上产生一个新的贡献。因此，$x=1\sim n-1$时的答案皆为$f_{n-1}$，$x=n$时的答案为$f_{n-1}+1$，故

$$f_n=\frac{(n-1)×f_{n-1}+f_{n-1}+1}n=f_{n-1}+\frac1n $$

因此$f_n=1+\frac12+\frac13+...+\frac1n$，证毕（$f_n$的名字叫调和级数）。

---

调和级数没有通项公式，数学上有近似公式$\sum_{i=1}^n\frac1i=\ln(n)+γ$，$γ$为欧拉常数，其值为$0.577215664...$
鄙人很废，背不下来这么个数字，所以就用分段打表法咯o(TヘTo)

分段打表是什么意思呢？就这题来说，比如你要求$n=10^8$时的答案，那么你先把$n=9×10^7$的答案，即$f_{9×10^7}$，求出来存到程序里，在询问时，直接从$f_{9×10^7}$开始$+\frac1{9×10^7+1}+\frac1{9×10^7+2}+...+\frac1{10^8}$，就可以将复杂度降到$O(10^7)$啦！

所以，我们只需要隔一段距离预处理出一个答案，询问时从已经求出的答案开始计算，就可以降低复杂度。以下给出我的代码，包括题目程序以及打表的辅助程序。

$Sol$

#include <cstdio>
using namespace std;
const int L = 1 << 26; //每隔1 << 26预处理一个答案
const long long data[1 << 5] = {
0x0000000000000000,
0x4032995ad72ecae3,
0x40334accef169efe,
0x4033b2997ec44843,
0x4033fc3f0706710f,
0x4034355ef6940cd4,
0x4034640b96b6c4f6,
0x40348b8201f6859f,
0x4034adb11efa431d,
0x4034cbd82667fc2d,
0x4034e6d10e88ab5c,
0x4034ff374e019d2a,
0x4035157daeabec2d,
0x403529fb5c77752c,
0x40353cf419ec0e29,
0x40354e9d9e3a9914,
0x40355f2336f014bc,
0x40356ea84f4fffb4,
0x40357d4a3e5e0699,
0x40358b2197d1130f,
0x40359843267ee387,
0x4035a4c0a99e4992,
0x4035b0a965f7fa74,
0x4035bc0a96ca6793,
0x4035c6efc6a269ae,
0x4035d163160dc644,
0x4035db6d746e0dd3,
0x4035e516ce106fe7,
0x4035ee6631e2be36,
0x4035f761f089a6be,
0x4036000fb63157f4,
0x40360874a021f9bc,
};
const double *list = (double*) data;

int n;

int main(){
	scanf("%d", &n);
	register double ans = list[n / L];
	for(register int i = n / L * L + 1; i <= n; i++)
		ans += 1.0 / i;
	printf("%.08f", ans);
	return 0;
}

打表机

#include <cstdio>
using namespace std;
const int L = 1 << 26;

double ans;

int main(){
	printf("0x%08x%08x,\n", *((int*)&ans + 1), ans);
	for(int i = 1; i < (1u << 31); i++){
		ans += 1.0 / i;
		if(i % L == 0) printf("0x%08x%08x,\n", *((int*)&ans + 1), ans);
	}
	return 0;
}