ctyl's problem solving

競技プログラミングが主な話題です。

yukicoder No.41

★3 DP派生.無駄に3時間くらいかかりました・・

要約すると9以下で{ \displaystyle q = M/111111}を作る方法の数{ \displaystyle f(q,9)}を答えればいいので,

{ \displaystyle
f(n,9)=f(n-9,9)+f(n-8,8)+ \cdots +f(n-1,1)
} でOKだろうと思ったら実は違っていて111111円を1円玉111111枚でも表現可能なことを忘れていた.ということでDPで求めたfの階差が答えでした. 結局自力で解けたとは言いがたいので,次の★3は自力で解きたい!

yukicoder No.41

yukicoder No.41