2016-07-01から1ヶ月間の記事一覧
問題概要 k進法で0からn-1までの各桁の和mod kという数列があるので、異なる部分列の個数を求めよ。 k 解法 珍しくデータ構造系でない。良問。まず、部分列の個数は、各文字について、現れる次の位置に配るDPをやると重複なく数えられる。これでO(nk)のDPが…
問題概要 k進法で0からn-1までの各桁の和mod kという数列があるので、異なる部分列の個数を求めよ。 k 解法 珍しくデータ構造系でない。良問。まず、部分列の個数は、各文字について、現れる次の位置に配るDPをやると重複なく数えられる。これでO(nk)のDPが…