這題的狀態轉移方程應該是很好推的吧，如果推不出方程，那也不用擔心，多做點求期望的題就有感覺了。
設dp[i]表示當前在 已經投擲出 i個 不相同/相同 這個狀態時期望還需要投擲多少次。然後dp[0]就是答案
相同的情況：
dp[0] = 1 + dp[1]
dp[1] = 1 + ( (m-1)*dp[1] + dp[2] ) / m
dp[i] = 1 + ( (m-1)*dp[1] + dp[i+1] ) / m
...
dp[n] = 0;
我們拿出i和i+1項來
dp[i] = 1 + ( (m-1)*dp[1] + dp[i+1] ) / m
dp[i+1] = 1 + ( (m-1)*dp[1] + dp[i+2] ) / m
上下相減得 ：m * (dp[i] - dp[i+1]) = dp[i+1] - dp[i+2];
令 d[i] = dp[i] - dp[i+1]; 則d[]為公比為m的等比數列, 且d[0] = 1;
所以d[i] = m^i， 然後由列項相消得 dp[0] - dp[i+1] = m^0+m^1+.....+m^i;
令i+1 = n 則 dp[0] = m^0+m^1+.....+m^(n-1);
不相同的情況：
dp[0] = 1 + dp[1]
dp[1] = 1 + (dp[1] + (m-1) dp[2]) / m
dp[2] = 1 + (dp[1] + dp[2] + (m-2) dp[3]) / m
dp[i] = 1 + (dp[1] + dp[2] + ... dp[i] + (m-i)*dp[i+1]) / m
...
dp[n] = 0;
跟相同的情況一樣，選出 dp[i] 和 dp[i+1] 這兩行相減 得
dp[i] - dp[i+1] = (m-i-1)/m * (dp[i+1] - dp[i+2]);
令 d[i] = dp[i] - dp[i+1]. 則 d[i] = (m-i-1)/m * d[i+1], 且d[0] = 1;
這個公式看上去跟相同時的情況差不多，不過不能往下化簡了
但我們可以根據這個遞推關系式 求出每個d[i]，
然後再 對其列項相消 就可以發現 dp[0] = d[0] + d[1] + d[2] + ..... + d[n-1];
套這兩個公式，代碼很短就能AC了， 所以代碼也不給出
