闲话
下午补。
今日模拟赛 T3
小恶心。原题似乎是 pe444，但是好像不让写题解的样子？
反正不是原题啦，随便！
首先观察 \(E(111) = 5.2912\) 这个数值就很不对劲。扔进计算器发现 \(H(111) = 5.291243607252986\)。这里的 \(H\) 就是调和级数，常这么记。
然后猜了这个结论，也就是 \(S_0(n) = H(n)\)。
具体是咋证的呢？
我们假设现在翻开的牌上数的集合是 \(\mathbb A\)，它的补是 \(\mathbb B\)。有一个结论是如果 \(\max \mathbb A > \min \mathbb B\) 就和前面的最大值换，反之就不换。
比较显然？因为你可以选择的一定是 \(\max \mathbb A\)，选了一定是不劣的。这点也是需要自己看不见自己的牌才能决定的。
然后发现只有自己是后缀最大值时才会不换。假设当前的排列是 \(p\)，我们设 \(suff(i)\) 是 \(i\sim n\) 的最大值，我们要的就是 \(\sum[p_i = suff(i)]\) 的期望。
这个东西就是 \(H(n)\)。
看到前缀和就想到用生成函数来刻画。假设 \(H(n)\) 的生成函数是 \(F(x)\)，我们考虑表出 \(F(x)\)。
\(H(n)\) 的差分是 \(\dfrac{1}{n}\)，而这个东西是好表示的，就是 \(-\ln(1-x)\)，证明考虑对 \((1-x)^{-1}\) 做积分。场上以为是 x((1-x)^{-1})' 所以推了老半天错解
、于是 \(F(x) = \dfrac{-\ln(1-x)}{(1-x)}\)。
\(S_k(n)\) 的生成函数 \(F_k(x)\) 也好写出了，就是
我们想要得到一个优美的形式，容易想到求导后对比系数。
\[\begin{aligned} F_k'(x) &= \left(\frac{-\ln(1-x)}{(1-x)^{k + 1}}\right)' \\ &= \frac{(-\ln(1-x))'(1-x)^{k+1} - (k + 1)(1 - x)^{k}\ln(1-x) }{(1-x)^{2(k + 1)}} \\ &= (k + 1)\frac{-\ln(1 - x)}{(1-x)^{k + 2}} + \frac{1}{(1-x)^{k + 2}} \end{aligned}\]我们容易提取上面的式子两边的系数，也就是
\[(n + 1)S_k(n + 1) = \binom{k + 1 + n}{n} + (k + 1) S_{k + 1}(n) \]我们希望和 \(k\) 相关，因此让 \(k\) 大的导出 \(k\) 小的，也就是要把 \(S_{k + 1}\) 单独放在一遍，让 \(k\) 加 \(1\) 得到
\[kS_k(n) = (n + 1)S_{k - 1}(n + 1) - \binom{k + n}{n} \]也就是
\[S_k(n) = \frac{n + 1}{k}S_{k - 1}(n + 1) - \frac{1}{k}\binom{k + n}{n} \]到这里我们就可以快速地递归到 \(S_0(n)\) 后计算了，组合数可以 \(O(k)\) 地求得。
那我们如何得到 \(S_0(n)\) 呢？
\(n\) 较小时可以预处理 \(H(n)\)。\(n\) 较大时呢？可以发现答案对精度的要求并不高。因此我们容易想到
\(\gamma\) 是 Euler-Mascheroni 常数，约为 0.57721566490153286060651209。背不过也可以直接算一个出来，几秒钟就能得到小数点后 ⑨ 位精度！
code
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>; using vi = vector<int>; using vp = vector<pii>; using ll = long long;
using ull = unsigned long long; using db = double; using ld = long double; using lll = __int128_t;
template<typename T1, typename T2> T1 max(T1 a, T2 b) { return a > b ? a : b; }
template<typename T1, typename T2> T1 min(T1 a, T2 b) { return a < b ? a : b; }
#define multi int T; cin >> T; while ( T -- )
#define timer cerr << 1. * clock() / CLOCKS_PER_SEC << '\n';
#define iot ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = (s), i##_ = (t) - 1; i > i##_; -- i)
#define eb emplace_back
#define pb pop_back
const int N = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fll;
#define gamma 0.57721566490153286060651209
#define H(n) (__builtin_logl(n) + gamma)
ll k, n;
ld h[1000003];
ld S(int k, ll n) {
if (k == 0 and n <= 1e6) return h[n];
if (k == 0 and n > 1e6) return H(n);
ld ret = 1. / k;
rep(i,1,k) ret = ret / i * (n + i);
return S(k - 1, n + 1) / k * (n + 1) - ret;
}
signed main() {
iot; cout.unsetf(ios::fixed); cout.setf(ios::scientific); cout.precision(9);
cin >> k >> n;
rep(i,1,min(1e6, n + k + 1)) h[i] = h[i - 1] + (ld)1. / i;
cout << S(k, n) << '\n';
}