yukicoder No.1857 Gacha Addiction
橙diffが解けたので書く！
以下すべてpi=pi/sとする。
i回目で終了するケースを考える
これはi-1回目までに重複がなく、i回目に初めて重複が起きる
i回目までは無視してi-1回目までを考える。
これはΠ(1+pi)を展開した各項にfact[i-1]を掛け合わせたものになる(この展開は分割統治FFTでO(n(logn)^2))
具体的な例を用意して考える
(1+p0x)*(1+p1x)*(1+p2x)=1+(p0+p1+p2)x+(p0p1+p0p2+p1p2)x^2+(p0p1p2)x^3
2回で終わるパターン
(p0+p1+p2)*(p0+p1+p2)*fact[1]*2
3回で終わるパターン
(p0p1+p0p2+p1p2)*(p0+p1+p2)*fact[2]*3
4回で終わるパターン
(p0p1p2)*(p0+p1+p2)*fact[3]*4
Σv[i]*fact[i]*(i+1)
この中には終わるパターンがすべて含まれているが、終わらないパターンも含まれている
具体的には
2回で終わらないパターン
(p0*p1+p0*p2+p1*p0+p1*p2+p2*p0+p2*p1)*fact[1]*2
3回で終わらないパターン
(p0p1*p2+p0p2*p1+p1p2*p0)*fact[2]*3
Σv[i]*i*fact[i-1]*(i)=Σv[i]*i*fact[i]
なので
Σv[i]*fact[i]*(i+1)-Σv[i]*i*fact[i](添え字の調整は必要)
