题解 P1943 【LocalMaxima】

· · 题解

鄙人证明此题的方法。

计算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;
}