77

上のDPを応用して解いてみた。

基本的にtable[N] = Σtable[N - p_i]な訳だけど、Nを1から増やしながらやっていくと、例えばN=5のときに問題が起きる。
まず、5-2=3のときは1通りの作り方しかないので1通り加算される。5-3=2のときも1通り加算される。しかし、両者共に2+3と3+2であり、重複されてカウントされてしまっていることが分かる。
これを解決するためには、Floyd-Warshallっぽい(と個人的に思う)考え方でやってやればいい。つまり、素数をp_iまで使ったときに何通りの表し方があるかというのをtableに保存していく。こうすると、式の上では素数が昇順に並ぶので重複カウントを解消できる。しかし、このやり方にはtableを長くできない(固定長でしか解を求められない)という欠点がある。

偉い人達の考え方としては
Prime Partition -- from Wolfram MathWorld
Euler Transform -- from Wolfram MathWorld
とかがあげられてたけど、眠くて理解できないので後日読む。。