Luogu-SP1026

题面

分析

设dp[x]为已掷出x个面后到掷出所有面状态的期望次数，每个色子每面被掷出的概率是$ frac{1}{n} (,掷出x个面后再掷到已掷出面概率为) frac{i}{n} $ ,掷到未掷出面的概率为$ frac{n - i}{n} $,掷出后达到的状态分别为i与i+1，且掷出本身也增加一次次数，则有

[f[i] = frac{n-i}{n}f[i + 1] + frac{i}{n}f[i] + 1 ]

化简后有

[f[i] = f[i + 1] + frac{n}{n-i} ]

初始化f[n] = 0,答案为dp[0];

#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<algorithm>
#define lson x<<1
#define rson x<<1|1
#define ll long long
#define rint register int
#define mid ((st[x].l + st[x].r) >> 1)
using namespace std;
template <typename xxx> inline void read(xxx &x) {
	char c = getchar(),f = 1;x = 0;
	for(;c ^ '-' && !isdigit(c);c = getchar());
	if(c == '-') c = getchar(),f = -1;
	for(;isdigit(c);c = getchar()) x = (x<<1) + (x<<3) + (c ^ '0');
	x *= f;
}
template<typename xxx>void print(xxx x)
{
    if(x<0){putchar('-');x=-x;}
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
const int maxn = 100010;
const int inf = 0x7fffffff;
const int mod = 1e9 + 7;
double dp[maxn];
int main()
{
	int t,n;read(t);
	while(t--) {
		read(n);
		dp[n] = 0;
		for(rint i = n - 1;i >= 0; --i) 
			dp[i] = dp[i + 1]  + n * 1.0 / (n - i) * 1.0;		
		printf("%0.2lf
",dp[0]);
	}
	return 0;
}
/*

*/