Description

在OI界存在著一位傳奇選手——QQ，他總是以風格迥異的搞笑代碼受世人圍觀
某次某道題目的輸入是一個排列，他使用了以下偽代碼來生成數據
while 序列長度< n do
{
隨機生成一個整數屬亍[1,n]
如果這個數沒有出現過則加入序列尾
}
聰明的同學一定發現了，這樣生成數據是徆慢的，那么請你告訴QQ，生成一個n排列的期望隨機次數

Input

一個正整數n，表示需要生成一個n排列

Output

一個數表示期望隨機次數，保留整數

Sample Input

4

Sample Output

8(.333333…)

【友情提示】

輸出樣例的括號里表示答案的小數部分，但實際丌要求輸出
數學期望=sigma(概率* 權值)，本題中為期望隨機次數=sigma(概率*隨機次數)

Data Constraint

30%數據滿足 n≤3
80%數據滿足 n≤107
100%數據滿足 n≤231

Solution

• 這題是經典的概率期望題。

• 定義 fi 表示 序列長度為 i 時的期望隨機次數，不難根據題目的定義列出遞推式：fi=in?(fi+1)+n?in?(fi?1+1)

• 解得：

  fi=fi?1+nn?i

• 所以答案就是：

  ∑i=1nni

• 但然而數據范圍很大，單純的 O(N) 處理是會超時的。

• 于是兩個“高深”的算法便橫空出世了！

• • 打表！！！——每隔 107 打一個數，暴力處理！~

• • 運用 歐拉常數 與 調和級數 處理，在 N 很大時誤差極小；

  • 之后在 N≤107 時同樣暴力處理即可。

  • 具體公式為：

    Ans=logeN?Euler?N

Code

#include<cstdio> #include<cmath> using namespace std; const double Euler=0.57721566490153286060651209; int n; double ans; int main() {scanf("%d",&n);if(n>1e7) ans=log(n)+Euler; elsefor(int i=1;i<=n;i++) ans+=1.0/i;printf("%.0lf",n*ans); }

總結

以上是生活随笔為你收集整理的JZOJ 3885. 【长郡NOIP2014模拟10.22】搞笑的代码的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。