可以发现本题实际上是 SP1026 FAVDICE - Favorite Dice 的加强版，在那题当中，我尝试过使用顺推的方式，令 (dp_i) 表示已经取完 (i) 面需要的期望次数。那么有转移 (dp_i = frac{n - i + 1}{n}(dp_{i - 1} + 1) + frac{i}{n}(dp_i + 1)) 我们需要明确的一点是转移是从 (i - 1 ightarrow i / i ightarrow i)，可以明显的发现这里的条件概率和 (frac{n - i + 1}{n} + frac{i}{n} e 1) 显然这是不可能的，但实际上我们在顺推的时候，因为到达状态的不确定性，因此从初始状态到达每种状态时的概率是不一样的，换句话说，我们在 (dp) 转移时乘上的概率不是上面那种简单的分数，而应该是推导得出的概率，但由于我们推导概率是比较麻烦的，因此我们可以考虑使用逆推。为什么逆推会是正确的呢？因为我们在逆推的时候，大多数情况下结果状态是一定的，那么我们到终点的概率将会是 (100\%)，并且我们是从一种状态转移到其他状态，条件概率和必为 (1)，因此我们在转移的时候只需要乘上简单的条件概率即可。因此我们可以令 (dp_i) 表示已经掷到了 (i) 面，要掷完还需的期望次数。那么就有转移 (dp_i = frac{n - i}{n}(dp_{i + 1} + 1) + frac{i}{n}(dp_i + 1))，移项可得 (dp_i = dp_{i + 1} + frac{n}{n - i})。
因此，在以后的做题当中，我们选择逆推求期望，顺推算概率。因为从起点而来的概率不好算，但到终点的概率往往是 (1)，我们要算期望只需乘上条件概率即可。又因为起点概率是已知的，因此我们从起点顺推概率才是最方便的。
本题也是一样的，我们先考虑最后答案的式子，必然是 (frac{k(k + 1)}{2} = frac{k ^ 2 + k}{2} = frac{k ^ 2}{2} + frac{k}{2}) 的形式，根据期望的线性性，我们将前后两个部分分开考虑计算贡献。不难发现后面的部分实际上就是上面提到的这道题，我们要做的就是求 (k ^ 2) 的期望。由 WJMZBMR打osu! / Easy 的经验，我们可以知道 ((k + 1) ^ 2 = k ^ 2 + 2k + 1)，于是我们只需要在计算 (k ^ 2) 的时候顺带维护线性的期望即可。具体来说，我们令 (f_i, g_i) 分别为已经掷完 (i) 面还需次数期望为 (k)，(k ^ 2) 的期望次数和 (k) 的期望次数。可以发现这里的 (g_i) 就是上面的 (dp_i) 于是我们有转移 (g_i = g_{i + 1} + frac{n}{n - i})，且有 (f_i = frac{n - i}{n}(f_{i + 1} + 2 imes g_{i + 1} + 1) + frac{i}{n}(f_{i} + 2 imes g_{i} + 1)) 化简移项后可得 (f_i = f_{i + 1} + 2 imes g_{i + 1} + frac{2i}{n - i}g_i + frac{n}{n - i})。从后往前逆推即可，答案即 (frac{f_0 + g_0}{2}).
#include<bits/stdc++.h>
using namespace std;
#define N 10000 + 5
#define dep(i, l, r) for(int i = r; i >= l; --i)
int n;
double f[N], g[N];
int read(){
char c; int x = 0, f = 1;
c = getchar();
while(c > '9' || c < '0'){ if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int main(){
n = read();
dep(i, 0, n - 1){
g[i] = g[i + 1] + 1.0 * n / (n - i);
f[i] = f[i + 1] + 2.0 * g[i + 1] + 2.0 * i / (n - i) * g[i] + 1.0 * n / (n - i);
}
printf("%.2f", (f[0] + g[0]) / 2);
return 0;
}