技術メモ

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

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

Python 数学

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

凄く大きい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

参考サイト

How to find the value of nCr%1000000007 for the large number n (n <= 10^6) in C - Quora
モジュラ逆数 - Wikipedia

mが素数以外の場合も :
nCr mod mの求め方 - uwicoder - アットウィキ

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

参考サイト

m3u8 stream to mp4 using ffmpeg · GitHub

円周率素数　ネイピア数素数

数学

3.14159265
と言われて何を思い浮かべるだろうか。
そう、円周率である。

円周率と言えば、3.1415...と続く数なのは小学生でも周知の事実だが、
円周率を頭から数えたとき出てくる素数というのはあまり知られていないかもしれない。

まず
3
は素数
31
も素数
314
は素数ではない
31415
も素数ではない
314159
は素数

こう見てみると、素数って意外と多いんじゃないかと思うかもしれない。
しかし次に素数が現れるのはなんと38桁目の


31415926535897932384626433832795028841
となる。


いやちょっと待てよ、円周率もやったならネイピア数もやってあげないと可哀想じゃないか
と思ったので、ネイピア数(e=2.71828...)でも同じことをやってみた。

まず
2
は素数
27
は素数ではない
271
は素数
2718
は素数ではない


...と続けていけば


2718281

2718281828459045235360287471352662497757247093699959574966967627724076630353547594571

と続き、

1781桁目、2780桁目に素数が見つかることがわかる。*1*2


27182818284590452353602874713526624977572470936999595749669676277240766303535475945713821785251664274274663919320030599218174135966290435729003342952605956307381323286279434907632338298807531952510190115738341879307021540891499348841675092447614606680822648001684774118537423454424371075390777449920695517027618386062613313845830007520449338265602976067371132007093287091274437470472306969772093101416928368190255151086574637721112523897844250569536967707854499699679468644549059879316368892300987931277361782154249992295763514822082698951936680331825288693984964651058209392398294887933203625094431173012381970684161403970198376793206832823764648042953118023287825098194558153017567173613320698112509961818815930416903515988885193458072738667385894228792284998920868058257492796104841984443634632449684875602336248270419786232090021609902353043699418491463140934317381436405462531520961836908887070167683964243781405927145635490613031072085103837505101157477041718986106873969655212671546889570350354021234078498193343210681701210056278802351930332247450158539047304199577770935036604169973297250886876966403555707162268447162560798826517871341951246652010305921236677194325278675398558944896970964097545918569563802363701621120477427228364896134225164450781824423529486363721417402388934412479635743702637552944483379980161254922785092577825620926226483262779333865664816277251640191059004916449982893150566047258027786318641551956532442586982946959308019152987211725563475463964479101459040905862984967912874068705048958586717479854667757573205681288459205413340539220001137863009455606881667400169842055804033637953764520304024322566135278369511778838638744396625322498506549958862342818997077332761717839280349465014345588970719425863987727547109629537415211151368350627526023


27182818284590452353602874713526624977572470936999595749669676277240766303535475945713821785251664274274663919320030599218174135966290435729003342952605956307381323286279434907632338298807531952510190115738341879307021540891499348841675092447614606680822648001684774118537423454424371075390777449920695517027618386062613313845830007520449338265602976067371132007093287091274437470472306969772093101416928368190255151086574637721112523897844250569536967707854499699679468644549059879316368892300987931277361782154249992295763514822082698951936680331825288693984964651058209392398294887933203625094431173012381970684161403970198376793206832823764648042953118023287825098194558153017567173613320698112509961818815930416903515988885193458072738667385894228792284998920868058257492796104841984443634632449684875602336248270419786232090021609902353043699418491463140934317381436405462531520961836908887070167683964243781405927145635490613031072085103837505101157477041718986106873969655212671546889570350354021234078498193343210681701210056278802351930332247450158539047304199577770935036604169973297250886876966403555707162268447162560798826517871341951246652010305921236677194325278675398558944896970964097545918569563802363701621120477427228364896134225164450781824423529486363721417402388934412479635743702637552944483379980161254922785092577825620926226483262779333865664816277251640191059004916449982893150566047258027786318641551956532442586982946959308019152987211725563475463964479101459040905862984967912874068705048958586717479854667757573205681288459205413340539220001137863009455606881667400169842055804033637953764520304024322566135278369511778838638744396625322498506549958862342818997077332761717839280349465014345588970719425863987727547109629537415211151368350627526023264847287039207643100595841166120545297030236472549296669381151373227536450988890313602057248176585118063036442812314965507047510254465011727211555194866850800368532281831521960037356252794495158284188294787610852639813955990067376482922443752871846245780361929819713991475644882626039033814418232625150974827987779964373089970388867782271383605772978824125611907176639465070633045279546618550966661856647097113444740160704626215680717481877844371436988218559670959102596862002353718588748569652200050311734392073211390803293634479727355955277349071783793421637012050054513263835440001863239914907054797780566978533580489669062951194324730995876552368128590413832411607226029983305353708761389396391779574540161372236187893652605381558415871869255386061647798340254351284396129460352913325942794904337299085731580290958631382683291477116396337092400316894586360606458459251269946557248391865642097526850823075442545993769170419777800853627309417101634349076964237222943523661255725088147792231519747

素数って楽しいですね。

*1:確率的素数判定法を使っているので厳密には「素数である可能性が非常に高い」ということです

*2:合成数なのに素数と判定されてしまう確率はおよそ4^{-50}