技術メモ

役に立てる技術的な何か、時々自分用の覚書。幅広く色々なことに興味があります。

nCk (mod m) の求め方 [n,kが凄く大きい場合]

大きいnに対してコンビネーションを求める

凄く大きいnに対してCombinationを求める時、例えば {}_{1000} \mathrm{C}_{400}を求めようと思っても愚直に計算するにはプログラムで扱える桁数を超えてしまう。
そこで、mで割った余り(modular)  {}_n \mathrm{C}_k \pmod{m}を求めさせることがある。

pythonで書いたのでサンプルコードを載せておく。
ただし、これを使うにはmはnを超える素数でないといけない

サンプルコード

再帰を使っている。

def mod_combination(n, k, mod):
    # nCk (mod m)
    def mod_permutation(n, k, mod):
        if n<=k:
            return 1
        else:
            return (n * mod_permutation(n-1,k,mod))%mod

    def mod_inv_permutation(k, mod):
        k, mod = int(k), int(mod)
        if k<=1:
            return 1
        else:
            return (pow(k,mod-2,mod) * mod_inv_permutation(k-1, mod))%mod

    return (mod_permutation(n,n-k,mod) * mod_inv_permutation(k, mod))%mod

理屈

割り算に対してモジュラ(余り)を計算するにはどうするかという問題がある。
それにはモジュラ逆数を考える必要がある。
プログラムでは

pow(k, mod-2, mod)

にあたる部分でモジュラー逆数を使っている。

モジュラ逆数とはa^{-1}\equiv x \pmod{m}となるxのこと。

結論から言うと

素数 mと互いに素な aに対して
 a^{-1}\equiv a^{m-2} \pmod{m}

となることを使っている。

(証明)
オイラー関数 \phi(m)を用いて、mが素数の時
\displaystyle
\left\{
\begin{array}{1}
 a^{\phi(m)}\equiv 1 \pmod{m}\\
 \phi(m) = m-1 
\end{array}
\right .
なので

a^{\phi(m) - 1} \equiv a^{-1} \pmod{m} \\
a^{m-2} \equiv a^{-1} \pmod{m}
(Q.E.D)

したがって {}_n \mathrm{C}_k (n < m)に対して

\begin{eqnarray}
{}_n \mathrm{C}_k & =  & n(n-1)\dots(n-k) \times k^{-1}(k-1)^{-1}\dots 1^{-1} \\
& \equiv &  n(n-1)\dots(n-k)\times k^{m-2}(k-1)^{m-2}\dots 1^{m-2} \pmod{m}
\end{eqnarray}


上のプログラムでは

def mod_permutation(n, k, mod)

 n(n-1)\dots(n-k) \pmod{m}  を

def mod_inv_permutation(n, k, mod)

 k^{m-2}(k-1)^{m-2}\dots 1^{m-2} \pmod{m} を
計算している。

おまけ

素数を確認したい時pythonではsympyを使おう

from sympy import isprime
print(isprime(1000000007)) #True

ffmpegを使って.m3u8(ストリーミング形式ファイル)の動画を.mp4形式で保存する

シェルスクリプトを書いた。

注意

使っていたffmpegのバージョンが少し古かった。最新版ではできない可能性もある。

ffmpeg version 2.8.4 Copyright (c) 2000-2015 the FFmpeg developers
built with gcc 5.2.0 (GCC)

スクリプト

名前は適当でいいが、例えば convert_m3u8_to_mp4.sh として保存

echo "filename: $1"
echo -n "input quality (default:20) => "
read QUALITY

ffmpeg -i $1 -bsf:a aac_adtstoasc -vcodec copy -c copy -crf ${QUALITY:=20} ${1%.*}".mp4"

実行例

sh convert_m3u8_to_mp4.sh test.m3u8

と引数に変換したいm3u8ファイルを指定。

input quality (default:20) =>

と聞かれるので、動画の品質を指定。
crf値と品質の関係は以下のようなサイトを参考に。
x264のcrf値はどれくらいが適切なのか? | もにっき
http://www.kurobuti.com/blog/?p=2131

うまく最後まで実行されればm3u8ファイルと同じ名前のmp4ファイルができるはず。
(つまり実行例の例で言うとtest.mp4)

ffmpegを使って動画のトリミング

ffmpeg -ss 00:00:30.0 -i input.wmv -c copy -t 00:00:10.0 output.wmv
  • -ssで開始時点を指定

終了タイミングを指定するのは、動画の長さを指定するか終了時点を指定する二つの方法がある。

  • -tでトリミングする動画の時間長さを指定
  • -toで終了時点を指定

command line - Using ffmpeg to cut up video - Super User