きままにものづくり

日々の気付いたことなんかを書いてます。

2013-09-01から1ヶ月間の記事一覧

MOD指数演算

指数演算は容易にオーバーフローしてしまうので、MODをとる場合でも工夫が必要である。 指数演算の場合の工夫は、MOD乗算の場合と非常に似ている。 指数をの足し算で表す。 ここで、は2進数表記でのnビット目を示す。ただし、0ビットから始まるとする。 この…

MOD乗算

MODをとる場合でも大きい数字の掛け算はオーバーフローしてしまうので、工夫をしなければならない。 片方の数字をの足し算で表す。 ここで、は2進数表記でのnビット目を示す。ただし、0ビットから始まるとする。 aを括弧内に入れる。 は1か0しか値を取らない…

最長増加部分列

目次 最長増加部分列とは アルゴリズム 最長増加部分列とは? 与えられるデータの配列をaとする。 かつ を満たす最長の部分列のこと。 アルゴリズム 最長増加部分列の個数を求めるアルゴリズムを説明する。 漸化式の作り方は2種類ある。 dp[i] := を最後の要…

動的計画法

動的計画法に関しての説明をする。 最長増加部分列問題 重複組合せ