人才网站建设策划书,wordpress rss解析,网站域名在哪买,成都市住房和城乡建设厅网站正题
题目链接:https://www.luogu.org/problemnew/show/P1943 题目大意
定义LocalLocalLocal数为一个数且比它前面的数字都要大。
求一个随机长度为nnn的序列中LoaclLoaclLoacl数的期望数量。 解题思路 ansLocal(a)n!ans\frac{Local(a)}{n!}ansn!Local(a)
现在我们分开求…正题
题目链接:https://www.luogu.org/problemnew/show/P1943 题目大意
定义LocalLocalLocal数为一个数且比它前面的数字都要大。
求一个随机长度为nnn的序列中LoaclLoaclLoacl数的期望数量。 解题思路
ansLocal(a)n!ans\frac{Local(a)}{n!}ansn!Local(a)
现在我们分开求先考虑如何求出所有序列中LocalLocalLocal数的数量
一个数xxx有x−1x-1x−1个数比他小那么若一个数成为LocalLocalLocal数的排列数是 ∑k1xPk−1x−1∗Pn−xn−xPx−1k−1∗(n−x)!\sum_{k1}^xP_{k-1}^{x-1}*P_{n-x}^{n-x}P^{k-1}_{x-1}*(n-x)!k1∑xPk−1x−1∗Pn−xn−xPx−1k−1∗(n−x)! 也就是答案为 ∑x1n∑k1x(Px−1−1)∗(n−x)!n!\sum_{x1}^n\frac{\sum_{k1}^x(P^{-1}_{x-1})*(n-x)!}{n!}x1∑nn!∑k1x(Px−1−1)∗(n−x)! 打表得(我不会证明啊) ⇒∑x1n1x\Rightarrow \sum_{x1}^n\frac{1}{x}⇒x1∑nx1
然后过掉n≤1000000n \leq 1000000n≤1000000的点然后使出调和级数 ∑x1n1xlog(n1)r(n→∞)\sum_{x1}^n\frac{1}{x}\log (n1)r(n\rightarrow \infty)x1∑nx1log(n1)r(n→∞) rrr为欧拉函数r≈0.5772156649r\approx 0.5772156649r≈0.5772156649
鬼知道考试的时候谁做的出来\color{white}\text{鬼知道考试的时候谁做的出来}鬼知道考试的时候谁做的出来 codecodecode
// luogu-judger-enable-o2
#includecstdio
#includecmath
using namespace std;
double n,ans;
int main()
{scanf(%lf,n);if(n1000000)for(int i1;in;i)ans((double)1/i);else anslog(n1)0.5772156649;printf(%.8lf,ans);
}
