https://csacademy.com/contest/round-75
初参加です。
A
はい。
B
変なdfsした
C
sort and lower_bound
D
priority_queue
E
平方分割でmodが小さい時はsegtreeで愚直に、大きい時は二分探索と思ったんですが通らず…。
F
NTTやるんですが、式変形だけ書いておきます。
f(i)=(N-i+1)!Σ(k=i-1...N)[(k-1)/2](k-2)!/(k-i+1)!
=(N-i+1)!Σ(u=0...N-i+1)[(u+i-2)/2](u+i-3)!/u!
<=>f(N-1-l)=l!Σ(u=0...l)[(N-1+u-l)/2](N-2+u-l)!/u!
=l!Σ(u=0...l)F(u)G(l-u)
ただしF(i)=1/i!,G(i)=[(N-1-i)/2](N-2-i)!
となってNTTの式に変換できました。
