読者です 読者をやめる 読者になる 読者になる

maroonさんのお正月問題

ヒント1 : FMTは使わない(MODが変な意味はない)

ヒント2 : 式の形は、個数に対応するハッシュではなく意味がある

おまけ

解法があってるかは未検証です。

ヒント1 : 係数がどうしようもなくなったので、長さごとにその長さの数列たちの和を独立に計算します

ヒント2 : 「長さ200,000の数列(各要素は109とか)を全部かけてください、ただしModではなく多倍長でそのまま」 を普通に順番に掛けるより早く計算するにはどうする?