Assignment 題目探討

題目概況

嗯。。。首先這是一道題，題目大概的意思是每次輸入兩個整數m,n有一個元素個數為m的一個不下降序列，它其中的元素大小均在[1,n]$[1,n]$之間且為整數。每個這樣的序列都有相等的概率被取到，問這個序列中眾數的出現次數的期望是多少。這里的眾數出現次數指的是一個序列中出現最多的一個數字（如果有多個數字出現次數最多，那么任取其一）出現的個數

舉個栗子，一個不下降序列: 1 2 3 3 3 4 4 5 5 7 7 7 8

它里面的眾數的出現次數即為3，這是因為3和7出現次數最多，這個次數為3

數據范圍

有至多15組數據，且1<=m<=250$1<=m<=250$,1<=n<=1?109$1<=n<=1*10^9$

解法

本題實際并不復雜，正常人的第一想法就是使用DP，這一點我們可以通過觀察m,n$m,n$的各自的大小得出。而這個想法也是正確的。我們考慮f(pos,k)$f(pos,k)$，它表示我們目前考慮到了第pos$pos$個元素，它目前在第k$k$段中，這種情況下的分段的方案數。下面考慮遞推式：

考慮遞推式，我們每次搞到一個新位置，它可以與上一個元素的段相同，也可以與上一個元素的段不同，所以我們很容易先想到這樣的式子：

f(pos,k)=f(pos?1,k)+f(pos?1,k?1)$f(pos,k)=f(pos-1,k)+f(pos-1,k-1)$

由于本題讓我們求出一個期望值，這時候我們就不能直接使用這個式子，因為這個式子它不能反映出眾數的出現次數。所以我們再考慮P(l)$P(l)$，它表示眾數出現次數為l$l$時的概率。然后對每個P(l)$P(l)$分別求解，再搞一搞本題就完成啦O(∩_∩)O~

然而。。。這種情況下的遞推式該怎么寫呢？我們要做的肯定是去排除不符合條件的情況，即數字出現次數超過了l$l$的情況

那么，就會有如下兩種遞推式。本題的重點就是，究竟哪一種是正確的呢：

A:f(pos,k)=f(pos?1,k)+f(pos?1,k?1)?f(pos?l,k)$A : f(pos,k)=f(pos-1,k)+f(pos-1,k-1)-f(pos-l,k)$

B:f(pos,k)=f(pos?1,k)+f(pos?1,k?1)?f(pos?1?l,k?1)$B : f(pos,k)=f(pos-1,k)+f(pos-1,k-1)-f(pos-1-l,k-1)$

（其實就我個人而言我覺得它們都是錯誤的。。。。）

還有就是DP邊界值的問題，究竟是應該定義f(0,0)=1$f(0,0)=1$呢還是應該定義f(1,1)=1$f(1,1)=1$呢還是什么別的。。。

也（yi）許（ding）是我太弱了QAQ，在這些問題上糾結了好久（其實現在想得也不是很明白），終于從整個遞推式的推導過程感覺參考題解得出來了一個結論。為了防止本蒟蒻誤導各位同學，我不在這里闡述結論。如果各位神犇有興趣的話可以下方評論，共同交流探討

代碼

雖然有標程但是并不想貼