ferinの競プロ帳

競プロについてのメモ

2020 ICPC Shanghai Site E. The Journey of Geor Autumn

問題ページ

dp[長さiの数列] = 何通り とDPをする。

1をi番目に置く

  • [1,i) は自由においてok → P(n-1, i-1)
  • (i,n] は dp[n-i] 通り

 \displaystyle dp \lbrack i \rbrack  = \sum_{j=1}^{\min(i,k)} P(i-1,j-1) * dp \lbrack i-j \rbrack  = (i-1)! \sum_{j=1}^{\min(i,k)} dp \lbrack i-j \rbrack  / (i-j)!

 dp \lbrack i-j \rbrack / (i-j)! の累積和をもちつつ更新すれば  O(n)