bestcoder #56 div 2 B Clarke and problem(dp)

果然dp還是弱項啊啊啊啊..
不過比最開始的完全無從下手強了不少應該...

至少dp狀態表示相對了....轉移方程沒想出來嗚嗚嗚

官方題解:设d(i, j)d(i,j)表示前ii个数,模pp为jj的方案数,则容易得到d(0, 0)=1, d(i, j)=d(i-1, j)+sum_{j=0}^{p-1} d(i-1, (j-a[i]) mod p)d(0,0)=1,d(i,j)=d(i1,j)+j=0p1​​d(i1,(ja[i]) mod p),很多人没1a是因为没注意|a_i| le 10^9ai​​109​​

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz